Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This could be mathematics or computer science, but also statistical physics, so I hope it qualifies for interest :) I am aware that there were reservations about the proof but no fatal flaws. I have followed Terence Tao's blog and Tim Gowers, both of whom have reservations, but Deolalikar is sticking with his assertions and was supposedly preparing an updated response to the critics. I haven't seen anything much since posts in August. Is anyone aware of any new updates more recent than Sept?

P=NP problem statement

status of paper

share|cite|improve this question

migrated from Feb 6 '11 at 21:15

This question came from our site for active researchers, academics and students of physics.

It was my understanding that Terence Tao felt that there was no hope of recovery:

"To give a (somewhat artificial) analogy: as I see it now, the paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with an advanced fuel injection system to get 200 miles to the gallon.

The FO(LFP) objections are like a discovery of serious wiring faults in the engine, but the inventor then claims that one can easily fix this by replacing the engine with another, slightly less sophisticated engine.

The XORSAT and solution space objections are like a discovery that, according to the blueprints, the car would run just as well if the gasoline fuel was replaced with ordinary tap water. As far as I can tell, the response to this seems to be equivalent to “That objection is invalid – everyone knows that cars can’t run on water.”

The pp/ppp objection is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engine. " Terence Tao at P=NP and Godel's Lost Letter

share|cite|improve this answer

Even though Deolalikar's paper was the most seriously considered recently, and a lot of work was put into it by important people in the few weeks after it came out, but very little public judgement since then. There were enough reservations that people probably won't bother looking at it again until the update comes out.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.