Slashdot Mirror
How the Web Rallied To Review the P != NP Claim
An anonymous reader writes "Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, the proof hasn't held up. But blogs and news sites helped spur a massive, open, collaborative effort on the Internet to understand the paper and to see if its ideas could be extended. This article explains what happened, how the proof was supposed to work, and why it failed."
This quote pretty much sums it up: “Even at a conference you don’t get this kind of interaction happening,” says Suresh Venkatasubramanian of the University of Utah. “It was like the Nerd Superbowl.”
This summary had three hyperlinks:
1. "claimed he had a proof"
2. "hasn't held up"
3. "spur a massive effort"
It was missing the only IMPORTANT hyperlink:
4. "this article". --- The slashdot submission was about an article. I'd like to read the article. I'd like a hyperlink which unambiguously takes me to the article. As it was, I didn't know which of the hyperlinks would take me to the article.
1. "claimed he had a proof" -- did this hyperlink take me to his claim? No: it took me to a online collaborative discussion of his claim (i.e. the original slashdot article).
2. "didn't hold up" -- did this hyperlink take me to the announcement that it didn't hold up? No: it took me to a slashdot article that maybe had a link to the statement about how it didn't hold up.
3. "spur a massive effort" -- did this hyperlink take me to that effort? Or did it take me to the spur in question? No: it took me to a REVIEW of that effort.
The hyperlinks in Slashdot summaries are always confusing.
This is definitely the kind of thing complexity theorists say. The argument fails entirely because it relies on our intuition of what easy means, and easy is not the same as polynomial, so transferring the intuition is almost intentionally misleading (not that I'm blaming you). It is basing a serious argument on an non-serious characterization of polynomial=easy that it used to help out-siders who don't know what polynomial means to never the less appreciate somewhat what complexity theory is about.
I think it's the opposite.
It's basing a non-serious argument on a serious characterization of the mathematical notion of complexity.
It's the original question, "why isn't there a simple proof of P != NP?" that is based on the layman's notion of "easy".
That the answer replaces the vague notion of "easy", with the accurately defined term "polynomial", and replaces the specific "is there an easy answer for this proof?" with the more general "proofs are NP-complete, and so we can expect it to be more complex than polynomial, assuming the thing we're trying prove is true", is not a failing of the answerer.
It's also not the failing of the questioner for being a layman. The point is, sometimes the correct answer to a question can't be put in the terms you want it to be and must, in essence, answer a different question. There are only two correct answers to the original query: "The proof of P!=NP is in the class of NP-complete problems", and "We won't know until we find it (or find the proof that P=NP)".
I personally feel one of the two conveys more useful information.
If someone asked you "How long will it take me to solve a specific but unknown instance of the Traveling Salesman problem?", you could either say: "The Traveling Salesman problem is in general NP-complete, so probably a long time", or you could say "Give me the problem and I'll let you know when I've solved it."
Since the search to find the actual solution, and thus as a side effect figure out how complex it is, is currently underway and in fact the topic of this discussion, that in the interim leaves only one useful answer.
The enemies of Democracy are
The proof tried to show that 3-SAT is not solvable in polynomial time. But the same techniques (if valid) would have also proven that 2-SAT (a simpler version of 3-SAT) is not solvable in polynomial time. That's a problem since we already have techniques for solving 2-SAT in polynomial time. In general if your proof technique can be used to prove something known to not be true, then your proof technique is broken.
The "relativization" barrier is similar. In trying to prove "P!=NP", it is really easy to also end up accidentally "proving" for certain oracles "X" that "P^X!=NP^X" when we already know that for those oracles "P^X=NP^X". The converse is also true: In trying to prove "P=NP" it is really easy to also end up accidentally "proving" for certain oracles "Y" that "P^Y=NP^Y" when we already know that for those oracles "P^Y!=NP^Y".