(0,1)-vector XOR problem this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. have seen similar problems in the literature but not this one in particular.

will write it in terms of bit-vectors because thats easiest for me. 


  let there be a set of bit-vectors of size $n$, $v_1, v_2, v_3, ... , v_n$. consider the bitwise XOR operation. given a target vector $v_0$. find a subset of vectors such that the bitwise XOR of the set equals the target vector. what is an efficient (or ideally, optimal) algorithm to find a subset?


the brute force algorithm enumerates the powerset of size $2^n$ and lists the 1st subset found. (slightly?) more efficient would look at 1-positions in the target and exclude subsets that do not have at least 1 vector with a 1 in a 1-position of the target.

the subset may or may not exist. it may or may not be unique.

closely related questions: (1) find the smallest subset, (2) output T/F depending on whether such a subset exists.

have a suspicion one of these problems is NP complete.

looking for references, insight etc. it would be interesting to know if there are "hard" vs "easy" inputs etc

as I wrote on the other question this seems closely related to the subset sum problem (see eg garey &amp; johnson ref) which is known to be NP complete but this seems to have "slightly" less complexity because its simpler to compute a vector bitwise XOR than a binary sum (the sum can have more binary digits).

the problem also seems closely connected to bin fu's recent question [2]

[1] https://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors

[2] Algorithmic Vector Problem
Let $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$. The problem is to determine whether the following system has a solution:

$$
\begin{pmatrix}
v_1 &amp; \cdots &amp; v_n
\end{pmatrix}
\begin{pmatrix}
x_1 \\
\vdots \\
x_n
\end{pmatrix}
=
v_0 \, (\text{mod } 2)
$$

This problem is known to be $\oplus L$-complete by [Damm90, BDHM92], thus inside $\text{NC}^2 \subseteq \text{P}$.

[Damm90] Carsten Damm: Problems Complete for $\oplus L$. Inf. Process. Lett. 36(5): 247-250 (1990)
[BDHM92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223-237 (1992)