How the Web Rallied To Review the P != NP Claim 160
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."
Nerd Superbowl (Score:4, Interesting)
Re:A simpler proof? Please? (Score:2, Interesting)
that simpler way would only exist if P = NP
Why? I can only guess your reasoning. Correct me if I am wrong:
"Proving P=NP can be accomplished by finding a polynomial time algorithm to the NP-hard problem of your choice. You give the problem, the algorithm, you prove is correct and that is poly-time. Success.
Proving P!=NP is the same (by definition) that proving that there is a problem in NP for wich there is no poly-time algorithm that solves it. Infinite problems and infinite algorithms... looks that proving no matching exists is necessarily hard."
It is not the case. For example, you can prove that not all sets are decidible by a simple cardinality argument. Infinite sets and infinite algorithms, but the infinites are not the same and you are done. You do not have to give a single example. It turns out that you can draw a parallel between "computable" and "computable in poly time". Many computablility proofs can be adapted to prove computability in poly-time. A nasty glitch is the P!=NP claim, which would be analogous to the existence of undecidible sets. The cardinality argument fails to prove P!=NP. :-)
Len Adleman taught me this, or at least that is what I understood
My point is that impossibility proofs are not always hard.
Re:Obvious or oblivious? (Score:2, Interesting)
It is the greatest question in computer science. A negative answer would likely give a fundamentally deeper understanding of the nature of computation. And a positive answer would transform our world: Computers would acquire mind-boggling powers such as near-perfect translation, speech recognition and object identification; the hardest questions in mathematics would melt like butter under computation’s power; and current computer security methods would be as easy to crack as a TSA-approved suitcase lock.
Proof that P!=NP: We haven't made any really hard problems really easy. If P=NP, then computers automatically acquire mind-boggling powers and the ability to crack encryption. Presumably that would have already happened if P=NP, therefor P!=NP. QED.
Following that logic, the world was flat until Galileo stated otherwise.
Really.... we humans are ignorant enough that we could be footling around with a limited set of algorithms for aeons and not stumble on any that solve NP problems. This isn't QED, it just shows that our set of known algorithms is painfully limited.
Think about Quicksort: that's an algorithm that really opened my eyes to P=?NP, as it showed how you could really optimize a sort by limiting the scope of the elements being sorted. I had never come up with quicksort by myself, and so it showed me how solutions can exist that we just haven't seen before. Such solutions will continue to pour in... possibly including solutions that provide binary computational engines with heretofore unbelievably powerful computing powers.
Think of it like this... HDD manufacturers were coming up against a known density limit, which meant that they theoretically couldn't manufacture platters with any higher density of information... so what happened? Instead of throwing in the towel and saying "well, time to find some other way to store information," some enterprising soul thought "well, what happens if we make the charges vertical instead of horizontal?" This is the kind of reasoning that is applied to P (and possibly NP) problems to create more efficient solutions. Often, it just takes a re-analysis of the base assumptions to find a novel way of completing a task. Believing that P==NP would go a long way towards having a more robust P set, even if no NP solutions were ever discovered.
Re:A simpler proof? Please? (Score:2, Interesting)
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. Even ignoring that, if P=NP and we are pretending that easy=polynomial, then proofs are only hard because we haven't proven that P=NP at this time. Our intution is based on what is easy for us now, so all we have learned then is that, indeed, we don't now have access to a polynomial algorithm for making proofs. So the argument fails even if we overlook the slight-of-hand to replace "polynomial" by "easy".
Additionally, proving that P=NP need not be easy or have a short proof even if it is true. As you have just pointed out, it would require coming up with an algorithm that can prove anything in mathematics, every field, in polynomial time. That algorithm might well be monstrosly complicated. On the other hand, there might be a simple one-page proof that P!=NP. There is no way to tell.
slashdot has confusing hyperlinks in its summaries (Score:5, Interesting)
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.
Re:Pi, what a waste of time (Score:3, Interesting)
Take a CAD program and figure the area of a circle of radius one. In some cases you get an interesting value of pi.
--
pi = 22/7. 22/7 repeats. Therefore pi is not transcendental.
Re:A simpler proof? Please? (Score:4, Interesting)
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.
Re:To summarize where the proof went wrong... (Score:4, Interesting)
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".