# Subset ${\tt XOR}$ problem

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?

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