I assume you have the polytope $P$ of dimension $d$ specified by a set of points, and a set of facets $\mathcal{F}$ where each facet is a subset of $P$ spanning a $d-1$-dimensional polygon. I'm not assuming that $P\subset\{0,1\}^d$: it could be in some $d$-dimensional subspace of $\mathbb{R}^D$ or $\{0,1\}^D$ for some $D\ge d$.
For computational efficiency, I'll assume that for each vertex $v\in P$, we have a list denoted $\mathcal{F}_v$ containing all faces in $\mathcal{F}$ containing $v$.
If $P$ is a polytope, it is topologically equivalent to a $d$-ball, $B_d$, which makes its boundary (surface) $\partial P$ topologically equivalent to a $d-1$-sphere, $S_{d-1}$. Hence, if the complex (surface) induced by the facets in $\mathcal{F}$ (which I'll just denote by $\mathcal{F}$) covers the entire boundary of $P$, $\mathcal{F}$ should be a sphere and hence have no boundary. If $\mathcal{F}$ has a boundary, it does not cover all of $\partial P$; in this case, at least some of the faces of $\mathcal{F}$ that make up $F$ must contain part of the boundary of $\mathcal{F}$. Thus, what we need to do is check if any of the faces in $\mathcal{F}$ contain any boundary.
Let's take one face, $F\in\mathcal{F}$. Since $F$ is a $d-1$-dimensional polygon, its facets are $d-2$-dimensional polygons. A facet of $F$ lies on the border of $\mathcal{F}$ if and only if it is not the facet of any other facet in $\mathcal{F}$. Thus, the question is if the list of facets of $F$ we can obtain by intersecting it with other facets in $\mathcal{F}$ covers the entire boundary of $F$.
This is exactly the same question as we started with, just posed for each facet of $P$ rather than for $P$ itself, and so in one dimension lower! Hence, all we need do is run this test recursively until we get down to the vertices.
Note that the intersection of two facets $F,F'\in\mathcal{F}$ can also provide $k$-facets with lower dimension ($k<d-2$), e.g. when two facets meet at a corner, which we do not include as facets of $F$.
Example: Let $P$ be a square $ABCD$, and let $\mathcal{F}$ contain the edges $AB$, $BC$ and $CD$. For the facet $BC$, intersecting $BC$ with the two other lines provides the facets $B$ and $C$, so $BC$ is not on the border of $\mathcal{F}$. However, for the facet $AB$, only $B$ is found to be shared with another facet, so $A$ is on the border of $\mathcal{F}$.
I'm sure trying to program this would uncover technical issues I haven't thought of, but I'm pretty sure the ide should work. Speedwise, it should be proportional to the number of different sequences $(F_0,F_1,\ldots,F_{d-1})$ where $F_{d-1}\in\mathcal{F}$ and $F_k$ is a facet of $F_{k+1}$ which separates $F_k$ from some other facet of $F_{k+1}$. E.g. if the $k$-dimensional facets of $P$ each have $\nu_k$ facets, that would make the time bounded by $\nu_1\nu_2\cdots\nu_{d-1}\cdot|\mathcal{F}|$; if the facets are all simplexes, this becomes $d!\cdot|\mathcal{F}|$.
Here are a few fail-fast tests: i.e. that can indicate that the set of facets is incomplete, but is not guaranteed to do so.
Let $\mathcal{F}^{(k)}$ denote the set of $k$-facets of $P$ induced by $\mathcal{F}$: i.e. $\mathcal{F}^{(d)}=\{P\}$ is the full polytope, $\mathcal{F}^{(d-1)}=\mathcal{F}$ are the known facets, $\mathcal{F}^{(d-2)}$ are $d-2$-dimensional polytopes generated from the intersection of two facets, etc., to $\mathcal{F}^{(0)}$ which are the vertices that can be generated from intersections of facets from $\mathcal{F}$. I.e. $\mathcal{F}^{(\cdot)}$ contains all non-empty intersections of sets of facets from $\mathcal{F}$ grouped by their dimension.
If $\mathcal{F}$ contains all facets of $P$, then $\mathcal{F}^{(k)}$ should contain all $k$-facets of $P$, and the following should hold:
(1) The $0$-facets, $\mathcal{F}^{(0)}$, should contain all vertices of $P$. This is the same as saying that, for $\mathcal{F}_v$ the set of facets that contain the vertex $v\in P$, $v$ is the only vertex contained in all of them: i.e. the intersection $\cup_{F\in\mathcal{F}_v}F=\{v\}$.
(2) We can generalise (1) a bit to make it more strict. E.g. the intersections of facets in $\mathcal{F}_v$ should not only produce the $0$-facet $\{v\}$, but also a number of $1$-facets, $2$-facets, etc.: at least two of each, but if facets are themselves convex polytopes there must be more of them.
(3) If $f_k=\dim\mathcal{F}^{(k)}$, as in the original problem proposal, the Euler characteristic $\chi(\mathcal{F})=f_0-f_1+\cdots+(-1)^df_d$ should be equal to $\chi(P)=1$ (which is true since $P$ is contractible).
Examples where these fail are:
(1a) A tetrahedron with $\mathcal{F}$ lacking one of the sides.
(1b) Let $P$ be an octahedron with vertices $R=[1,0,0]$, $L=[-1,0,0]$, $F=[0,1,0]$, $B=[0,-1,0]$, $U=[0,0,1]$, $D=[0,0,-1]$ (right, left, forward, backward, up, down): I'm sure you can embed this in $\{0,1\}^D$ for some $D$. While $P$ has 8 faces, we let $\mathcal{F}=\{RFU,LBU,RBD,LFD\}$. The six vertices all occur as intersections of faces from $\mathcal{F}$: we'd have to look at the edges to see that $\mathcal{F}^{(\cdot)}$ is incomplete.
(2) An icosahedron with $\mathcal{F}$ lacking one side.
(3) Let $P$ be a cube, and let $\mathcal{F}$ consist only of two opposing sides. Since all intersections of faces in $\mathcal{F}$ are empty, we get $f_0=f_1=0$, $f_2=2$, $f_3=1$ which makes $\chi(\mathcal{F})=1$.
