6 ms·

Sounds very click-baity. 1) Quantum computers are not able to solve NP-complete problems. They have their own complexity class, BQP, that is suspected to be di

Sounds very click-baity. 1) Quantum computers are not able to solve NP-complete problems. They have their own complexity class, BQP, that is suspected to be disjunct from the class of NP-complete problems. 2) If they solved just one configuration, like it said in the article, that doesn't prove anything. They must be able to solve any problems in that class of problems. 3) However, even if they "just" found a way to solve an NP-complete problem 10000 times more energy efficiently, that's impressive, even if it won't scale. (And it won't, because it's NP-complete.) Just don't do those clickbait things, OK?

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 ago
  Yes, because transforming a problem in one class of NP-complete problems into another is itself a problem in P.
- 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.
YeGoblynQueenne 11y ago
>> Sounds very click-baity. Oh dear. Not again :) [Edit: by that I mean that I had another sumbission in the same day that readers considered had a clickbaity title] I guess I could have changed the title to "NP Complete problem tackled with parallel computation using biological motors" or something similar- that would have been more informative and less of a strong claim. But the submission guidelines also say to avoid changing the title (unless it's clickbaity) so in some case you just have to make a judgment. I think in this case the title is a bit ambiguous. You could read it as "NP complete problem class solved" or "NP complete problem instance solved". But I think the author makes a good job of detailing the result, they do link back to the original paper and there's plenty more to the article than just a catchy title. Also it's on Ars, that generally has a good record of not trying to pull the wool over their readers' eyes. So really, I didn't think it would be read as an attempt at generating an undeserved er, buzz. So I erred on the side of keeping the title as it was. Well, anyway- this was a bit unexpected (two titles read as clickbaity in one day) so I'm a bit worried now- I don't want to come across as a ... clickbaiter? I'll err on the side of caution on the next few submissions and see what happens.
- GolDDranks 11y ago
  No worries, it's the title of the original article, and I'm criticising mainly that. But the article itself definitely has it's own share of problems/inaccuracies.

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 ago
Yes, because transforming a problem in one class of NP-complete problems into another is itself a problem in P.
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.

YeGoblynQueenne 11y ago

>> Sounds very click-baity. Oh dear. Not again :) [Edit: by that I mean that I had another sumbission in the same day that readers considered had a clickbaity title] I guess I could have changed the title to "NP Complete problem tackled with parallel computation using biological motors" or something similar- that would have been more informative and less of a strong claim. But the submission guidelines also say to avoid changing the title (unless it's clickbaity) so in some case you just have to make a judgment. I think in this case the title is a bit ambiguous. You could read it as "NP complete problem class solved" or "NP complete problem instance solved". But I think the author makes a good job of detailing the result, they do link back to the original paper and there's plenty more to the article than just a catchy title. Also it's on Ars, that generally has a good record of not trying to pull the wool over their readers' eyes. So really, I didn't think it would be read as an attempt at generating an undeserved er, buzz. So I erred on the side of keeping the title as it was. Well, anyway- this was a bit unexpected (two titles read as clickbaity in one day) so I'm a bit worried now- I don't want to come across as a ... clickbaiter? I'll err on the side of caution on the next few submissions and see what happens.

GolDDranks 11y ago
No worries, it's the title of the original article, and I'm criticising mainly that. But the article itself definitely has it's own share of problems/inaccuracies.