Emptiness of complement of subspace arrangement Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem? 

P.S.: It seems that this can be reduced to the computation of a characteristic polynomial, which looks like a hard problem. Is there another route?
Your problem is coNP-hard. 
Take a 3SAT instance with variables $X$ and clause set $C$. 


Set the dimension in your problem to $n:=|X|$.
For every clause $c\in C$, introduce a corresponding $(n-3)$-dimensional subspace $S(c)$ by restricting the three dimensions that correspond to the three variables in $c$.
If a variable occurrs positively in $c$, then fix the corresponding coordinate at 0.
If a variable occurrs negatively in $c$, then fix the corresponding coordinate at 1.
A 0-1 truth assignment (to the variables in $X$) violates clause $c$, if and only if the vector corresponding to the truth assignment lies in subspace $S(c)$.
A 0-1 truth assignment (to the variables in $X$) satisfies all clauses,
if and only if the vector corresponding to the truth assignment lies in none of the subspaces $S(c)$.