3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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)$.
$\endgroup$
  • $\begingroup$ Thanks for the quick response! That was straightforward enough :) $\endgroup$ – arnab Feb 9 '15 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.