4 ms·
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 communicatio
by 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 agoPeople 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 agoThat'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 agoI 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.