3 ms·
You're confusing solving an instance of subset-sum with solving subset-sum. If you solve subset-sum, yes, you've solved all NP-complete problems. If you solve
by hiddencost 11y ago
You're confusing solving an instance of subset-sum with solving subset-sum.
If you solve subset-sum, yes, you've solved all NP-complete problems.
If you solve an instance of subset-sum, you've only solved that instance of subset-sum.
The issue here is that to show you've solved subset sum, you need to show that you've solved it for _all possible inputs_.
Subset sum is "given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?".
If I give you the set {-2, -1, 0, 1, 2}, you can tell me in O(n) time that a subset of this sums to zero.
That doesn't mean you've solved subset sum, it means you've solved an instance of subset sum. To solve subset sum, you need to provide a proof showing that you have an algorithm that works for ANY set.
The work here gets results for a specific configuration. To show it solving subset-sum, it would need to be shown to work for all possible sets.