Emptiness of complement of subspace arrangement

Question

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?

Answer 1

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)$.