4 ms·
Isn't solving one NP-complete problem solving all NP-complete problems? Reducibility is how you almost always prove something is NP-complete.
by jon_richards 11y ago
Isn't solving one NP-complete problem solving all NP-complete problems? Reducibility is how you almost always prove something is NP-complete.
- GolDDranks 11y agoYes, because transforming a problem in one class of NP-complete problems into another is itself a problem in P.
- hiddencost 11y agoYou'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.