… 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? Something like that). It was a great few weeks: I learned a lot and met a number of people for the first time who I know to this day. 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. 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. I remember staying up two nights in a row working through this paper with people like Harvey Greenberg. At the end, we identified a hole in the proof. Swart changed things around a bit, and I lost track of where things went: 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. I left it there.
If I had been brilliant, I might have asked the question whether you could prove that this type of formulation cannot work. I’m not that brilliant, but Mihalis Yannakakis is, and he proved shortly thereafter that any symmetric formulation for this problem requires exponential size.
Since then, it is stunning how often proofs that P=NP (or P not equal to NP) crop up. Gerhard Woeginger does the field a tremendous service by collecting pointers to papers that try to prove the question one way or the other. The rate of production for these sorts of results seems to be growing, with 10 papers in 2008 and 2009. I very much like Gerhard’s obsessive neutrality in this. 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”.
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. There are always people out there who do work through things, and find the flaws. The Geomblog has a nice parody of how the process goes, and that does match up nicely with my experience 20 years ago. And this post is not an invitation to send me your proof of P=NP or P!=NP!
Despite the “crankiness” that comes from the P(!)=NP papers, I do think good comes out of this work. For instance, Swart’s paper led to Yannikakis’ very significant result. And reviewing these papers (once or twice, anyway) is great training for doing referee work in our field.
Thanks to @hakmem whose tweet got me looking at these sites again.
Thanks for this Mike; and for the link to Gerhard’s page. I agree, he does a fantastic job and his page on P, NP and P=NP is a useful starting point for anybody interested in the subject.
I vaguely recall Arvind Rajan talking about pulling an all-nighter hacking through Swart’s proof at the same ARIDAM. (We overlapped as Bixby students. Arvind graduated a few years before and, like many bright OR folks, abandoned OR for Wall Street.)
I attended a later ARIDAM during which a Canadian OR professor seemingly had a nervous breakdown right in front of us. Oh, and László Lovász taught a week-long workshop too. I remember the former event more graphically.
They sure were eventful conferences. The Late Peter Hammer was responsible, if I remember right.