4 ms·
> I have yet to see a convincing argument that it's not http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p
by modulus1 11y ago
> I have yet to see a convincing argument that it's not
http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858
Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps.
...
My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.
...
The moral is that people should distinguish between known (or knowable) polynomial-time algorithms and arbitrary polynomial-time algorithms. People might never be able to implement a polynomial-time-worst-case algorithm for satisfiability, even though P happens to equal N P.
- mcguire 11y agoOn the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]: "So, OK, why should you believe P≠NP? Here’s why: "Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false." [1] http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720
- SilasX 11y agoI think they're agreeing on the major substantive issue, that we won't reach a world where "composing a symphony is just as easy as enjoying it" -- Aaronson, because P != NP, and Knuth, because the proof of P=NP will not provide a polynomial-time algorithm for NP-complete problems.
- danbruc 11y agoThis symphony thing comes up again and again but it seems pretty silly to me. Enjoying and composing a symphony requires understanding what makes a piece of music sound good to humans, undoubtedly a nontrivial problem, but is it really hard to imagine that once that got formalized one can use this information to search the space of all possible pieces of music for beautiful symphonies in a not terrible inefficient way? I don't think so.
- deleted 11y ago[deleted]
- eru 11y agoThat's not too surprising. Most NP-hard problems are pretty tractable in practice.
- devilsavocado 11y agoBut is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bit problem in NP space in n^M steps. Knuth himself prefaces his argument by saying that it is naive! His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.
- algorias 11y agoThe argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all those problems are clearly in NP.
- baddox 11y agoThe time hierarchy theorem does not state that there are NP-complete problems that cannot be solved in polynomial time. If it stated that and was well-accepted, then there would be no P ?= NP mystery.