Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a 64-bit positive integer $y$ and a set of $100$ $64$-bit positive integers: $X = \{ x_1, x_2, \dots, x_{100} \}$

I want to find a smallest possible $Z = \{z_1, z_2, \dots, z_n\} \subset X$, such that:

$$\begin{align} y = z_1 ⊕ z_2 ⊕ \dots ⊕ z_n \end{align}$$

if such a $Z$ exists.

Clearly there are $2^{100}$ possible subsets of $X$, so iterating through them would take too long.

Does anyone know of, or can anyone think of, some sort of dynamic programming solution or other feasible algorithm?

share|improve this question
    
Relevant: Subset sum problem –  user2468 Apr 1 '12 at 1:00
    
@J.D.: No, I think because it's XOR and not addition that it is not NP-Complete. I'm sure there is a solution that takes advantage of the independence of the bit positions in XOR, I just can't see it. –  Andrew Tomazos Apr 1 '12 at 1:19

1 Answer 1

up vote 1 down vote accepted

If you introduce binary variables $c_i$ that are $1$ when $x_i\in Z$ and $0$ otherwise, you can write

$$y=\bigoplus_ic_ix_i\;.$$

This is a $64\times100$ system of linear equations over the field $\mathbb F_2$ for the $c_i$ that you can easily solve using Gaussian elimination; the number of steps is of the order of a million. If the $x_i$ have full rank $64$, which is almost certain to be the case if they're randomly chosen with uniform distribution, the solution space will have $36$ dimensions, so you just need to enumerate $2^{36}$ different solutions to find the optimal one; this is doable in reasonable time on a present-day computer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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