patternMinor
Subset of numbers whose XOR has least Hamming weight
Viewed 0 times
xorwhosenumbersweighthasleastsubsethamming
Problem
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!
Solution
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.
Context
StackExchange Computer Science Q#75703, answer score: 6
Revisions (0)
No revisions yet.