9

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

Community
  • 1
vzn
  • 11,014
  • 2
  • 31
  • 64
  • 2
    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 Feb 26 '12 at 17:55

2 Answers2

18

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)

Michael Blondin
  • 2,582
  • 21
  • 22
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

Steven Stadnicki
  • 1,396
  • 6
  • 14