Subset ${\tt XOR}$ problem

Question

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?

Answer 1

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