[Computational Complexity] But This One Is Different...
- This summer I took a two part vacation: Touring Ireland July 26-August 5, with my wife to celebrate twenty years of marriage and a short trip to Santa Fe, Augut 9-12, to catch opera with my elder daughter. Let's talk about what happened in between.
On Friday, August 6, Vinay Deolaikar sent me and 21 of my closest frinds an email entitled "Proof announcement: P is not equal to NP". I took a quick look and white it did look better that most P/NP proof attempts (in the sense that Deolaikar doesn't make up his own notation), I spotted the following line in his write-up:
Distributions computed by LFP must satisfy this model.Many P versus NP attempts work by claiming that a polynomial-time algorithm must act a certain way forgetting that an algorithm can completely ignore any semantic meaning in the problem. Since LFP is just a fancy way of saying "polynomial-time algorithm", it looked like Deolaikar fell into the same trap. So I filed the paper into my Why Me? folder as I have with many many others and figured that was the end of that.
As you readers all know, on Sunday the 8th the paper was slashdotted and Lipton, impressed that Deolaikar worked on infinite Turing machines (whatever they are), posted on the proof saying he was "certainly hopeful". People then flooded with me with emails, tweets and instant messages asking me about the paper.
I read over Lipton's post and took another look at the paper and still didn't see the semantic approach outlined in the paper as a viable attack on the P versus NP problem. At this point I knew people I trust would look over the paper carefully so I wouldn't have too. I couldn't keep completely quiet so I tweeted
Much ado about an unverified proof. The word "must" is troubling. I'll let others check it carefully.In retrospect I should have been more negative. Kudos to Scott for taking a strong and risky stance.
The emails kept coming but I remembered my vacation message was still active and I didn't have to answer them. I went to Santa Fe and didn't check email until I returned.
There are two camps in our community on Deolaikar's paper. Those of us who saw Deolaikar's paper as just another in a long series of bad attempts at P v NP and wondering what all the fuss was about. And those who thought Deolaikar hit upon a new proof paradigm and despite the numerous problems, big and small, with the paper still hold hope something important will come out of it.
Deolaikar at this point should retract his P ≠ NP claim until he can address all these issues. In an email Deolaikar sent out to the gang of 22 on Friday the 13th, he restates his claim and overview of the proof and says he "fixed the issues in the finite model theory portion of the proof". He promises a revised version on his homepage in a couple of days.
Deolaikar is following the script, currently at stage 5 of the 12 stage process. Stage 6 will happen sooner than he expects.
Posted By Lance to Computational Complexity at 8/16/2010 07:33:00 AM