HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Subset of numbers whose XOR has least Hamming weight

Submitted by: @import:stackexchange-cs··
0
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.