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
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
Deolaikar is following the script, currently at stage 5 of the
stage process. Stage 6 will happen sooner than he expects.
Posted By Lance to Computational Complexity at 8/16/2010 07:33:00 AM