3
$\begingroup$

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$ complexity? I was thinking of some trie based implementation but don't think that will work at all. Would a dynamic programming approach work by any chance? If possible, a hint would be nice!

$\endgroup$
6
$\begingroup$

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.

$\endgroup$
  • $\begingroup$ Just making sure here - calculating the minimal distance of a (binary) linear code is finding the minimum no. of set bits in the XORs of each nonempty subset of the binary representations? $\endgroup$ – Indo Ubt May 20 '17 at 21:09
  • 1
    $\begingroup$ Yes, that's the same thing. $\endgroup$ – Yuval Filmus May 20 '17 at 21:14
  • $\begingroup$ Also, are there better algorithms (better than O(2^n)) used for calculating these distances? $\endgroup$ – Indo Ubt May 20 '17 at 21:19
  • 1
    $\begingroup$ That's possible, but unfortunately I'm not aware of any. Now that you know what to look for, you can find out on your own. $\endgroup$ – Yuval Filmus May 20 '17 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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