<p>As a followup to my comment: finding the smallest satisfying subset should in fact be NP-complete; the reduction is to the minimal-weight code problem (given a basis for a code over GF(2), what's the minimum-weight vector in the code?) and this was apparently proven NP-complete in 1997 by A. Vardy: "The intractability of computing the minimum distance of a code", <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542">http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542</a></p>

CC BY-SA 3.0
2012-02-26T22:55:16.800Z
If I remember right, Vardy uses a reduction from minimum subset-sum problem over finite fields of characteristic 2, which is known to be NP-complete and is indeed equivalent to what OP asks.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-02-27T14:53:11.053Z
Is there any approximation result for this problem?
Bin Fu
CC BY-SA 3.0
2014-01-05T20:49:17.267Z
@bin just ran across this ref that considers approximation variants [A Deterministic Reduction for the Gap Minimum
Distance Problem](http://www.cs.ou.edu/~qcheng/paper/gd.pdf) Cheng/Wan & cites other refs that may be helpful
vzn
CC BY-SA 3.0
2012-02-26T20:23:58.917Z
2012-02-26T20:23:58.917Z
Steven Stadnicki
<p>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:</p>

<p>$$
\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)
$$</p>

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

<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)</p>

CC BY-SA 3.0
2012-02-26T18:24:35.773Z
2012-02-26T18:35:58.113Z
2012-02-26T18:35:58.113Z
Michael Blondin
<p>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.</p>

<p>will write it in terms of bit-vectors because thats easiest for me. </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<p>the subset may or may not exist. it may or may not be unique.</p>

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

<p>have a suspicion one of these problems is NP complete.</p>

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

<p>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).</p>

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

<p>[1] <a href="https://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors">https://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors</a></p>

<p>[2] <a href="https://cstheory.stackexchange.com/questions/10327/algorithmic-vector-problem">Algorithmic Vector Problem</a></p>

CC BY-SA 3.0
2012-02-26T17:55:07.150Z
This problem is exactly the question 'is the vector $v_0$ in the span of the vectors $v_1..v_n$ modulo 2?'; if the $v_i$ are linearly independent mod 2 then all $v_0$ are and the problem can be solved by a matrix inversion; and even if the $v_i$ are not independent it should be readily solvable via gaussian elimination.  The 'smallest satisfying subset' problem _may_ be NP-complete - it's essentially asking 'what is the smallest-weight nonzero vector in the span of these vectors modulo 2?' - but I'm not conscious enough to have a precise answer to that yet.
Steven Stadnicki
<cc.complexity-theory><reference-request><circuit-complexity><lower-bounds>
(0,1)-vector XOR problem
vzn
# (0,1)-vector XOR problem

(Asked by: username_0 on 2012-02-26)

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 & 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](https://cstheory.stackexchange.com/questions/10327/algorithmic-vector-problem)

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, lower-bounds
> **Comments:**
> **username_1**: This problem is exactly the question 'is the vector $v_0$ in the span of the vectors $v_1..v_n$ modulo 2?'; if the $v_i$ are linearly independent mod 2 then all $v_0$ are and the problem can be solved by a matrix inversion; and even if the $v_i$ are not independent it should be readily solvable via gaussian elimination.  The 'smallest satisfying subset' problem _may_ be NP-complete - it's essentially asking 'what is the smallest-weight nonzero vector in the span of these vectors modulo 2?' - but I'm not conscious enough to have a precise answer to that yet.  

---

## 2 answers

### Answer by username_4 on 2012-02-26. Score: 18 | Accepted answer

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 & \cdots & 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)


---

### Answer by username_1 on 2012-02-26. Score: 13

As a followup to my comment: finding the smallest satisfying subset should in fact be NP-complete; the reduction is to the minimal-weight code problem (given a basis for a code over GF(2), what's the minimum-weight vector in the code?) and this was apparently proven NP-complete in 1997 by A. Vardy: "The intractability of computing the minimum distance of a code", <http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542>

> **Comments:**
> **username_2**: If I remember right, Vardy uses a reduction from minimum subset-sum problem over finite fields of characteristic 2, which is known to be NP-complete and is indeed equivalent to what OP asks.  
> **username_3**: Is there any approximation result for this problem?  
> **username_0**: @bin just ran across this ref that considers approximation variants [A Deterministic Reduction for the Gap Minimum Distance Problem](http://www.cs.ou.edu/~qcheng/paper/gd.pdf) Cheng/Wan & cites other refs that may be helpful  

---

