News for hackers. Stuff that matters.
Re:NP-complete problem solved with biological motors by jon_richards on Sunday February 28, 2016 @01:11AM (#11190062)
Isn't solving one NP-complete problem solving all NP-complete problems? Reducibility is how you almost always prove something is NP-complete.
Re:NP-complete problem solved with biological motors by hiddencost on Sunday February 28, 2016 @01:43AM (#11190123)
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.

Re:NP-complete problem solved with biological motors by GolDDranks on Sunday February 28, 2016 @01:20AM (#11190080)
Yes, because transforming a problem in one class of NP-complete problems into another is itself a problem in P.