… or not.<\/p>\n
About 20 years ago, I attended a summer program at RUTCOR<\/a> (the OR center at Rutgers) called, I believe, ARIDAM (Advanced Research Institute in Discrete Applied Mathematics?\u00a0 Something like that).\u00a0 It was a great few weeks:\u00a0 I learned a lot and met a number of people for the first time who I know to this day.\u00a0 If my memory holds, it was at that conference that we heard about work by a University of Guelph professor named Ted Swart that purported to prove that P=NP.\u00a0 In his paper, Swart gave a n^5 variable (or n^7) linear programming formulation for the hamiltonian path problem, along with a complicated case-by-case proof that this linear program had a solution if and only if the graph had a hamiltonian cycle.\u00a0 I remember staying up two nights in a row working through this paper with people like Harvey Greenberg<\/a>.\u00a0 At the end, we identified a hole in the proof.\u00a0 Swart changed things around a bit, and I lost track of where things went:\u00a0 I recall thinking that it was pretty clear that adding a subscript could get around any hole we found, but that any constant number of subscripts would leave ever-more-complicated holes in the proof.\u00a0 I left it there.<\/p>\n If I had been brilliant, I might have asked the question whether you could prove that this type of formulation cannot work.\u00a0 I’m not that brilliant, but Mihalis Yannakakis is, and he proved<\/a> shortly thereafter that any symmetric formulation for this problem requires exponential size.<\/p>\n Since then, it is stunning how often proofs that P=NP (or P not equal to NP) crop up.\u00a0 Gerhard Woeginger<\/a> does the field a tremendous service by collecting pointers to papers that try to prove the question one way or the other<\/a>.\u00a0\u00a0 The rate of production for these sorts of results seems to be growing, with 10 papers in 2008 and 2009.\u00a0 I very much like Gerhard’s obsessive neutrality in this.\u00a0 It is always “Professor X proves P=NP” when I would be tempted to write “Professor X claims to prove P=NP”, or even “Professor X has typed some stuff which only he thinks proves P=NP”.<\/p>\n Having spent hours twenty years ago with one of these types of proofs, I don’t feel an obligation to work through more of them.\u00a0 There are always people out there who do work through things, and find the flaws.\u00a0\u00a0 The Geomblog has a nice parody<\/a> of how the process goes, and that does match up nicely with my experience 20 years ago.\u00a0 And this post is not<\/em> an invitation to send me your proof of P=NP or P!=NP!<\/p>\n Despite the “crankiness” that comes from the P(!)=NP papers, I do think good comes out of this work.\u00a0 For instance, Swart’s paper led to Yannikakis’ very significant result.\u00a0 And reviewing these papers (once or twice, anyway) is great training for doing referee work in our field.<\/p>\n Thanks to @hakmem<\/a> whose tweet<\/a> got me looking at these sites again.<\/p>\n","protected":false},"excerpt":{"rendered":" … or not. About 20 years ago, I attended a summer program at RUTCOR (the OR center at Rutgers) called, I believe, ARIDAM (Advanced Research Institute in Discrete Applied Mathematics?\u00a0 Something like that).\u00a0 It was a great few weeks:\u00a0 I learned a lot and met a number of people for the first time who I … Continue reading “P=NP …”<\/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":[46],"tags":[],"class_list":["post-767","post","type-post","status-publish","format-standard","hentry","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/767","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=767"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/767\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}