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?
Emptiness of complement of subspace arrangement
co.combinatorics;computational geometry;arrangements;finite fields
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)$.