Possible Issues With the P != NP Proof 147
An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."
Current Status (Score:5, Informative)
The original discussion was in a Google Doc but has since moved to a wiki [michaelnielsen.org].
Info: Previous post explaining the proof more clearly [wordpress.com]
Paper [hp.com] (not wort reading for most of us)
Mathematicians are gathering to vet this paper (Score:5, Informative)
For anyone interested in the details, you can find a lot more on this wiki [michaelnielsen.org], where a lot of mathematicians are weighing in on the proof and its potential flaws. Mathematicians are gathering from all over to examine this paper because it's so interesting. Even if one of the serious objections that have been raised so far kills it, it contains some novel ideas that will get people thinking.
They've also been gathering the news coverage and such, so it's probably the best place to find up-to-date information about this proof. It seems to have sparked quite a lot of interest for a paper that hasn't even been properly published.
Yes, they've tried that (Score:5, Informative)
They've tried that, but all that's been proven so far is that several types of proof won't work, rather than proving that it's impossible to prove. The first few sections of this paper itself go into detail about why this proof isn't one of the kinds of proof that won't work, incidentally.
Terrence Tao has a blog post on why a P=NP proof can't be relativisable [wordpress.com] if you're interested. Incidentally, there are several other classes of proof that won't separate P from NP.
Re:Proof that a proof can't exist? (Score:4, Informative)
This question has been considered by quite a few different people; search google for P vs NP independent [google.com] ("independent" meaning independent from the usual accepted axioms for mathematics, i.e., can't be proven using the currently accepted axioms).
There's a nice survey paper about this question that's very readable if you're willing to invest some time: Is P Versus NP Formally Independent? [scottaaronson.com].
Re:How? (Score:5, Informative)
Dick Lipton (Score:4, Informative)
Re:Mathematicians are gathering to vet this paper (Score:3, Informative)
You don't REALLY need to CAPITALIZE words so FREQUENTLY to make your point.
Free vocabulary lesson. (Score:2, Informative)
Irregardless is not a valid word.