NP = P solved ?
in [Math]
|
Prev: improving my Goldbach proof without needing Galois Algebra #5.20 Correcting Math
Next: improving my Goldbach proof without needing Galois Algebra #5.21 Correcting Math
From: gudi on 12 Aug 2010 00:55 http://www.hindu.com/2010/08/12/stories/2010081257181300.htm Narasimham
From: Marko Amnell on 12 Aug 2010 07:49 "gudi" <mathma18(a)hotmail.com> wrote in message 15d2dc9d-3aa1-401e-84b0-e47be585d770(a)v35g2000prn.googlegroups.com... > http://www.hindu.com/2010/08/12/stories/2010081257181300.htm > > > Narasimham Vinay Deolalikar claims he has a proof that P != NP. But the experts don't buy it. The best online discussion of the subject is over at Richard Lipton's blog: http://rjlipton.wordpress.com/ A consensus has formed that is best expressed by Terence Tao: ------------------------------------------------------------ I think there are several levels to the basic question "Is the proof correct?": 1.Does Deolalikar's proof, after only minor changes, give a proof that P NP? 2.Does Deolalikar's proof, after major changes, give a proof that P NP? 3.Does the general proof strategy of Deolalikar (exploiting independence properties in random -SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results? After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is "No" (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is "Probably not, unless substantial new ideas are added." But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days.) http://rjlipton.wordpress.com/ ----------------------------------------------------------- Despite the many objections of experts, Deolalikar is standing by his claim to have a proof and is trying to respond to the criticisms. His homepage now states vis-�-vis his paper on P vs NP that: "Please note that the final version of the paper is under preparation and will be submitted to journal review."
From: Marko Amnell on 12 Aug 2010 08:18 "Marko Amnell" <marko.amnell(a)kolumbus.fi> wrote in message 8ci5e3F347U1(a)mid.individual.net... > A consensus has formed that is best expressed > by Terence Tao: Oops. Some characters were lost when I copy and pasted Tao's comment. Here is a more readable version: ------------------------------------------------------------ I think there are several levels to the basic question "Is the proof correct?": 1.Does Deolalikar's proof, after only minor changes, give a proof that P != NP? 2.Does Deolalikar's proof, after major changes, give a proof that P != NP? 3.Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results? After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is "No" (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is "Probably not, unless substantial new ideas are added." But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days.) http://rjlipton.wordpress.com/
From: Marko Amnell on 13 Aug 2010 05:18
"Marko Amnell" <marko.amnell(a)kolumbus.fi> wrote in message 8ci5e3F347U1(a)mid.individual.net... > > "gudi" <mathma18(a)hotmail.com> wrote in message > 15d2dc9d-3aa1-401e-84b0-e47be585d770(a)v35g2000prn.googlegroups.com... >> http://www.hindu.com/2010/08/12/stories/2010081257181300.htm >> >> >> Narasimham > > Vinay Deolalikar claims he has a proof that P != NP. > But the experts don't buy it. And the last nail in the coffin seems to have been hammered in today, with the release of a letter from Neil Immerman, an expert on Finite Model Theory, one of the theories used by Deolalikar in his purported proof, in which Immerman identifies a fatal flaw in Deolalikar's argument: http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ TechCrunch has a pretty good article on what just happened: http://techcrunch.com/2010/08/12/fuzzy-math/ What did happen is that a week ago, Vinay Deolalikar, a computer scientist at Hewlett-Packard in Palo Alto, California, sent a copy of an article to several leading experts in theoretical computer science, in which he claimed to have solved the P vs NP problem, perhaps the most important open problem in the field. What happened then was something unprecendented. Two days later, someone leaked Deolalikar's article to the public. Online, hundreds of computer scientists, mathematicians and engineers tore apart Deolalikar's article, finding numerous flaws in the argument. It was, as some have said, the most public peer review process in the history of the world. You can see a list of some of the flaws on a wiki page created to cover the event: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper There has never been anything like it. It did remind me a bit of the online discussions back in 1993 when Andrew Wiles announced that he had proved Fermat's Last Theorem. At the time, various experts came forward to analyse Wiles's paper online, and post summaries, analyses and explanations on Usenet. But the scale of the discussion in places like sci.math about Wiles was dwarfed by the scale of the discussion about Deolalikar's proof over the last five days. Back in 1993, there was no blogosphere like today. |