<p>Your problem is coNP-hard. 
Take a 3SAT instance with variables $X$ and clause set $C$. </p>

<ul>
<li>Set the dimension in your problem to $n:=|X|$.</li>
<li>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$.<br>
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.</li>
<li>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)$.</li>
<li>A 0-1 truth assignment (to the variables in $X$) satisfies all clauses,<br>
if and only if the vector corresponding to the truth assignment lies in none of the subspaces $S(c)$.</li>
</ul>

CC BY-SA 3.0
2015-02-09T16:56:08.563Z
Thanks for the quick response! That was straightforward enough :)
arnab
CC BY-SA 3.0
2015-02-09T10:19:19.800Z
2015-02-09T10:19:19.800Z
Gamow
<p>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>

<p>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?</p>

<co.combinatorics><computational-geometry><arrangements><finite-fields>
Emptiness of complement of subspace arrangement
arnab
# Emptiness of complement of subspace arrangement

(Asked by: username_0 on 2015-02-09)

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?

**Tags:** co.combinatorics, computational-geometry, arrangements, finite-fields

---

## 1 answers

### Answer by username_1 on 2015-02-09. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks for the quick response! That was straightforward enough :)  

---

