3 ms·

> if you can quickly solve NP problems, you basically have super powers. This classic argument is flawed, because P=NP doesn't mean that you can "easily" solve

> if you can quickly solve NP problems, you basically have super powers. This classic argument is flawed, because P=NP doesn't mean that you can "easily" solve all NP problems. Nature is still free to define huge exponents to difficult problems, making them essentially unsolvable in practice. I even heard Knuth recognizing this recently.

tgb 11y ago
Yes, of course, in the same sense that we might have faster than light communication (but just barely) and not be able to exploit it for meaningful communication backwards in time to make a killing on the stock market. But we can still think "wow, that sounds kind of absurd" as a metric by which to judge the likelihood of a result. Either way, this is Scott Aaronson's argument, not mine. For example, he makes it here: http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/limitsqc-draft.pdf
- coliveira 11y ago
  People like Scott Aaronson who spouse this view use it as a fundamental reason why NP=P should be false. The problem is exactly that it is a flawed argument. It could be an argument for the impossibility of finding "efficient" algorithms, but this is not what P=NP is about. For all we know, some problems in P could be so difficult as to preclude any practical algorithm.
  - tgb 11y ago
    That's true: it's essentially conflating "efficient" meaning in polynomial time with "efficient" in the colloquial sense. Still is enough to make me skeptical!
    - coliveira 11y ago
      I am in no way saying that this indicates that P=NP, so I am also skeptic. I am just pointing out that you should be skeptic for the right reasons, not because of a misused argument.
  - chazisop 11y ago
    > For all we know, some problems in P could be so difficult as to preclude any practical algorithm. You can actually prove that given any (concrete) subclass of P that there is a language in both in P and harder, by a simple application of the time hierarchy theorem.

tgb 11y ago

Yes, of course, in the same sense that we might have faster than light communication (but just barely) and not be able to exploit it for meaningful communication backwards in time to make a killing on the stock market. But we can still think "wow, that sounds kind of absurd" as a metric by which to judge the likelihood of a result. Either way, this is Scott Aaronson's argument, not mine. For example, he makes it here: http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/limitsqc-draft.pdf

coliveira 11y ago
People like Scott Aaronson who spouse this view use it as a fundamental reason why NP=P should be false. The problem is exactly that it is a flawed argument. It could be an argument for the impossibility of finding "efficient" algorithms, but this is not what P=NP is about. For all we know, some problems in P could be so difficult as to preclude any practical algorithm.
- tgb 11y ago
  That's true: it's essentially conflating "efficient" meaning in polynomial time with "efficient" in the colloquial sense. Still is enough to make me skeptical!
  - coliveira 11y ago
    I am in no way saying that this indicates that P=NP, so I am also skeptic. I am just pointing out that you should be skeptic for the right reasons, not because of a misused argument.
- chazisop 11y ago
  > For all we know, some problems in P could be so difficult as to preclude any practical algorithm. You can actually prove that given any (concrete) subclass of P that there is a language in both in P and harder, by a simple application of the time hierarchy theorem.