[Computational Complexity] Intelligent questions about the alleged P NE NP proof
- People have asked me how much the alleged proof of P NE NP was discussed at Barriers II. Actually, nobody discussed the proof; however, we did discuss the aftermath. Most of the discussion was about the same questions I had posted a few days ago. In fact, here is a direct quote: Your post mixed interesting questions, which were ignored, and stupid thoughts, which is all anyone commented on. Why don't you repost just the interesting questions?
SO, here is that posts questions, minus the stupid things I said, plus things I heard at the conference.
- Why did this proof get so much attention before it was verified? Because Lipton and Cook took it seriously.
- Was this all good for the community? YES- more people know what P vs NP is. YES- if Gowers and Tao now begin working on it more. YES- stone soup.
- Do mathematicians care about complexity theory? The answer is surely yes, but how strongly? Is the answer yes or Yes or YES or HELL YES! ? If you count number-of-mathematicians then its hard to say. If you take a weighted sum based on quality of mathematicians then Gowers and Tao alone make the weighted sum enormous. In any case, when did the change happen? Was it drastic or slow?
- If someone claims to prove a big result and its public and problems are found with the proof, should they retract? If so then by when? One thing problematic with the question is the word should. Should for the good of the field? Should for the good of ones own career? Should if you want to be taken seriously? If someone has minor mistakes and just needs a little more time to fix them then a retraction is not needed. But the terms minor mistakes and a little more time are not well defined.
- How much progress has been made on P vs NP? Scott thinks so. (See the talk Has there been progress P vs NP which is on his homepage.)
- Have there been hard math problems that were solved all-of-a-sudden without any real prior results or plan? Finding and intermediary c.e. degree was such a problem, but it wasn't anywhere near as hard or as important as P vs NP.
- What criteria SHOULD we use to determine if a proof of a major result is worth looking at?
- What criteria DO we use to determine if a proof of a major result is worth looking at?
- Has Descriptive Complexity Theory been ruled out as a way to solve P vs NP (something like oracles or natural proofs)?
- The story about the story has reached the New York Times: here
Posted By GASARCH to Computational Complexity at 9/01/2010 09:39:00 AM