[FOM] P NP buzz

Alasdair Urquhart urquhart at cs.toronto.edu
Wed Aug 11 09:59:11 EDT 2010

I agree with most of what Harvey Friedman says about the
Deolalikar proof, but I disagree with his statement
that the paper is written carefully.  I've read it
through, and in the key places, it has nothing resembling
rigorous definitions and proofs.

About 75% or more of the paper consists of general
remarks or exposition of already known material, and
this part is fine.  But the key part of the paper, Section 7, where the
proof of P \neq NP appears, is far from  rigorous.
The key notion of ENSP model is not clearly defined, but described
in a rather rambling fashion, accompanied by a coloured diagram.
The crucial Proposition 7.6 does not have a proof at all.
Rather, it appears abruptly in the middle of a meandering discussion.

The paper reads rather like rough notes stating a plan for settling
the question.  If Deolalikar wants the community to take his
ideas seriously, he needs to write them up in an acceptable
way.  It's not the job of the CS theory community to perform
exegetical research on what he might have meant.

Alasdair Urquhart

More information about the FOM mailing list