{"id":1193,"date":"2010-09-01T15:18:40","date_gmt":"2010-09-01T19:18:40","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1193"},"modified":"2010-09-01T15:18:40","modified_gmt":"2010-09-01T19:18:40","slug":"p-versus-np-and-the-research-process","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/09\/01\/p-versus-np-and-the-research-process\/","title":{"rendered":"P versus NP and the Research Process"},"content":{"rendered":"

By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar<\/a> of HP Labs.\u00a0 After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission.\u00a0 He claims:<\/p>\n

I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers.\u00a0 I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website.<\/p><\/blockquote>\n

I am convinced by Dick Lipton’s blog entry<\/a> and by Scott Aaronson’s commentary<\/a> suggesting fundamental flaws in the paper, but since Vinay has not retracted the paper, I will look forward to the definitive version of the paper.\u00a0 For a detailed description of the issues, press coverage, and other aspects, polymath has an extensive wiki on the topic<\/a>.<\/p>\n

What I find most intriguing is the field’s response to this claimed proof.\u00a0 Proofs that P=NP or P<>NP are certainly not uncommon.\u00a0 Gerhard Woeginger faithfully keeps track of these claims and is up to 62 in his list<\/a>.\u00a0 Some of these results come out of the operations research world.\u00a0 For instance, Moustapha Diaby<\/a> is a faculty member at the business school at the University of Connecticut and believes he has found linear programming formulations for NP-hard problems (number 17 on Woeginger’s list).<\/p>\n

The Deolalikar paper is unique, however, in that many, many top mathematicians looked very closely at the paper and worked very hard to determine its correctness.\u00a0 This group includes people like Fields-medal winner Terrence Tao<\/a> and Polya and Fulkerson prize winner Gil Kalai<\/a>.\u00a0 Why did so many very smart people (and successful!\u00a0 They don’t do wikipedia pages on just anyone [yet]) spend time on this while practically no one spends time with the other 61 purported proofs?<\/p>\n

The most obvious reason is that this paper presented a fundamentally new approach to this problem.\u00a0 As Lipton says<\/a>: “the author has advanced serious and refreshingly new ideas of definite value”.\u00a0 In this proof, Deolalikar uses finite model theory<\/a>, an area of logic, to deduce structures in random satisfiability problems.\u00a0 If P=NP, then the structures would have to be different than what is already known about random satisfiability problems in the critical region (this synopsis is vague to the point of not being usable). This is definitely a different direction than past efforts, bringing together a number of disparate fields.
\n<\/span><\/span><\/p>\n

Further, Deolalikar knows very well that there are a number of proofs in the literature that say “P<> NP cannot be proved this way”.\u00a0 For instance, any result that cannot distinguish between the easy 2-satisfiability and the hard 3-satisfiability is doomed to failure (Aaronson’s blog entry<\/a> gives a few others along with other signs to check for in claimed proofs). Deolalikar presented reasons for believing that his approach evaded the barriers.\u00a0\u00a0\u00a0 This leads to excitement!\u00a0 Could this approach avoid known invalid approaches? <\/span><\/span><\/p>\n

Contrast this with papers that suggest that a linear programming model can correctly formulate an NP-complete problem.\u00a0 Yannakakis showed that no symmetric formulation can do so<\/a>, and that provides a powerful barrier to linear programming formulations.\u00a0 Not only must a a formulation not be symmetric, but its asymmetry must be of the sort that continues to evade Yannakakis’ proof.\u00a0 Without a strong argument on why an LP formulation fundamentally avoids Yannakakis’ argument, it is not even worthwhile spending time with LP formulations of\u00a0 NP-complete problems. <\/span><\/span><\/p>\n

This overwhelming doubt was clearly not felt by some referees who allowed Diaby’s papers to be published in “International Journal of Operational Research”<\/a>, lending credence to the idea that the refereeing and journal process in operations research is broken (in my view, of course).\u00a0 For the steps given in the Computational Complexity blog<\/a>, we have have to add a step: “Your paper is accepted by a third tier journal and still no one believes it.”\u00a0 Similarly, it will not be enough for me to see that Deolalikar’s paper is published:\u00a0 at this point I trust the blogs (some of them, anyway) more than the journals!
\n<\/span><\/span><\/p>\n

Even if the Deolalikar result is shown not to be valid, the paper gives me enormous hope that someday the P<>NP (as I believe it is, rather than P=NP) will be proved.\u00a0 We appear to be developing methods that will have some traction in the area.
\n<\/span><\/span><\/p>\n


\n<\/span><\/span><\/p>\n


\n<\/span><\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar of HP Labs.\u00a0 After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission.\u00a0 He claims: I have fixed all the issues that were … Continue reading “P versus NP and the Research Process”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,32,46],"tags":[],"class_list":["post-1193","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-journals","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1193","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1193"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1193\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1193"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1193"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1193"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}