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!
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered May 20, 2017 at 21:05
-
$\begingroup$ Just making sure here -
calculating the minimal distance of a (binary) linear codeis finding the minimum no. of set bits in the XORs of each nonempty subset of the binary representations? $\endgroup$– Indo UbtCommented May 20, 2017 at 21:09 -
1$\begingroup$ Yes, that's the same thing. $\endgroup$ Commented May 20, 2017 at 21:14
-
$\begingroup$ Also, are there better algorithms (better than O(2^n)) used for calculating these distances? $\endgroup$– Indo UbtCommented May 20, 2017 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$ Commented May 20, 2017 at 21:22