9
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Commented Feb 26, 2012 at 17:55

2 Answers 2

Reset to default
18
$\begingroup$

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)

Improve this answer
$\endgroup$
13
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Mahdi Cheraghchi
    Commented Feb 26, 2012 at 22:55
  • 1
    $\begingroup$ Is there any approximation result for this problem? $\endgroup$
    – Bin Fu
    Commented Feb 27, 2012 at 14:53
  • $\begingroup$ @bin just ran across this ref that considers approximation variants A Deterministic Reduction for the Gap Minimum Distance Problem Cheng/Wan & cites other refs that may be helpful $\endgroup$
    – vzn
    Commented Jan 5, 2014 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.