[modulus1]

> I have yet to see a convincing argument that it's not

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]

On 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

[SilasX]

I 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]

This 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.

[eru]

That's not too surprising. Most NP-hard problems are pretty tractable in practice.

[devilsavocado]

But 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]

The 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]

The 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.

[algorias]

Correct, but I didn't claim what you are refuting. I just said that there is no upper bound to "how polynomiallly hard" a problem can get, i.e. Knuths intuition is wrong.

[baddox]

Look at the quote. Knuth is explicitly only talking about NP problems.