An Update On Vinay Deolalikar’s “Proof”
An view from some IBM theorists about the claimed proof that P does not equal NP
Ken Clarkson is one of the world experts on computational geometry. He is also a Senior Manager of Computer Science Principles and Methodologies at the IBM Almaden Research Center. Most impressive, in my opinion, he is one of Andy Yao’s Ph.D. students. Andy has had few students, relatively, and Ken is in an elite group.
Today I want to give a very short update on Vinay Deolalikar’s claimed proof of PNP.
Ron Fagin, Ken, and Ryan Williams gave a presentation recently at IBM Almaden on the claimed proof. It was an “IBMer’s Eyes Only” presentation. Ron has kindly released the presentation to the world—see this for the talk: video and slides. Here is where the link takes you to:
What’s all this about P not equaling NP?
Recently there was considerable interest in a proposed proof that P is not equal to NP. In response to that interest, some members of the theory group gave a talk to describe, for a general scientific audience, some aspects of this work and the community’s analysis of it. (The video starts a little bit into the talk; the speakers are Ken Clarkson, Ron Fagin, and Ryan Williams, in that order; the “D.” referred to is Vinay Deolalikar, the author of the proposed proof.)
Video of the talk (including all but the first few slides)
I have talked to Ryan about the presentation and he said it went well. There clearly is still great interest in the potential proof.
The Status of The “Proof”
As for the actual status of the Vinay’s “proof” I will add all I know, which is not much. Some is based on talking to people who do know and some on guess-work.
- Vinay recently gave a talk of his own at HP on his proof. The talk was very high level, and I understand that while interesting, it added little to the technical details.
- He is working on a “full” draft of the proof—it is getting much longer as all the details are added. Perhaps the “final” draft with be 200-300 pages in length.
- Finally, I have no idea if he will soon make the draft public, or if he has sent to to a journal. Or if he still plans to do that.
I suspect there are others who know much more, but that is all I know now.
A question that we are about to face is: how long should a claim of a great result remain unresolved? I think it is clearly in Vinay’s and the community’s interest to get the matter resolved soon. I still hope he is right, but I do hope that we get some closure soon.