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] http://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xorshttps://cstheory.stackexchange.com/questions/10341/building-0-1-vectors-out-of-xors
