3 ms·
Subset sum is actually only weakly NP-complete. What that means: best known algorithms are only exponential in terms of problem size (number of bits it takes to
by praptak 12y ago
Subset sum is actually only weakly NP-complete. What that means: best known algorithms are only exponential in terms of problem size (number of bits it takes to encode the numbers) but not in terms of the numbers themselves. Dynamic programming solves subset sum in Poly(numbers) time, which is obviously exponential in terms of bits.
So there's a danger here associated with demonstrating your superpowers on subset-sum: unless the numbers are huge, you are actually solving a trivial problem.
I didn't dig into the article enough to check whether the authors made this mistake.
- tlb 12y agoYes, they also make this mistake. The frequencies correspond to the numbers being summed, so if the numbers are huge (>100 bits) the frequencies will be so high that the wavelengths would be smaller than atoms, where you can't construct physical circuits. If you scale down the frequencies, the time it takes for a complete period goes up exponentially with the number of bits in the numbers.