1
$\begingroup$

Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.

Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset $S\subseteq X$ such that the the bitwise ${\tt XOR}$ of the members of $S$ is $0$ everywhere.

For example, et $n = 4$ and consider

  • $x_0 = {\tt 1 0 0 1}$

  • $x_1 = {\tt 0 1 0 1}$

  • $x_2 = {\tt 0 0 0 1}$

  • $x_3 = {\tt 1 1 0 0}$.

Then the bitwise ${\tt XOR}$ of $S = \{x_0, x_1, x_3\}$ is ${\tt 0000}$.

Question. This problem is clearly in ${\bf NP}$ as it is easy to check a proposed solution. Is it ${\bf NP}$-complete?

$\endgroup$

1 Answer 1

3
$\begingroup$

The problem is in $P$. It can be solved in polynomial time with Gaussian elimination.

Build a $n\times n$ boolean matrix $M$, whose $i$th row is the $i$th bit-string in $X$. All arithmetic will be modulo 2 (i.e., in $GF(2)$). Solve for a bit-string $v$ such that $Mv=0$ (and $v \ne 0$). Such a bit-string, if it exists, can be found using Gaussian elimination, as this is a system of $n$ linear equations in $n$ unknowns. Finally, any such bit-string $v$ yields a solution to your problem; the set $S$ includes the $i$th bit-string of $X$ iff $v_i=1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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