Theoretical Computer Science
- co.combinatorics computational-geometry arrangements finite-fields
- Updated Thu, 23 Jun 2022 20:19:00 GMT
-
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?
Solution
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)$.