[FOM] P NP buzz

[Harvey Friedman]

On Aug 11, 2010, at 9:59 AM, Alasdair Urquhart wrote:

> 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.


When I said "written carefully" I didn't mean "written carefully as a  
proof". More like "written carefully as a document". There is some  
warning near the beginning, if I remember, to the effect that details  
are omitted.

To date, the biggest red flag I've seen from people, in addition to  
Alasdair's comments above, are these two postings below of Russell  
Impagliazzo - posted on Richard Lipton's blog. Russell is somebody  
important in the field, that I know. In a sense, following this, I  
think people are implicitly - and later may explicitly - point a  
somewhat negative finger at Steve Cook branding it "appearing to be a  
relatively serious attempt at P vs. NP". However, in Steve's defense,  
he used the words "appear" and "relatively". I think Steve's ultimate  
defense, if he wants one, is that what Steve said is arguably true,  
but the counter to Steve is that what Steve said is - or can be viewed  
as - misleading.

Here's my question. Is Vinay the most accomplished and credentialed  
person (at the time of the circulation) to circulate an outright  
public claim to have solved P vs. NP?

Russell Impagliazzo PERMALINK
August 11, 2010 12:00 am
I am somewhat distressed to see so many people spending a lot of time  
on this.
It does not actually look like a serious attempt at P vs. NP to me. It  
does not seem
to have any original ideas, just an intuition that has been often  
expressed that
search spaces broken up into many clusters far apart are hard for  
standard search
algorithms (but as has been pointed out, can also be exhibited by  
problems in P,
such as solving linear equations.) I don’t see any real statement of a  
series of lemmas
that imply the main theorem, and the conclusions reached do not seem  
to be
supported by any claims made earlier.

I’d like to see a clearly articulated lemma that states the properties  
used that imply a
problem is not solvable in P. In particular, it should be possible to  
see that the properties
fail for random linear equations, or other easy instances of search  
problems.

Russell Impagliazzo PERMALINK
August 11, 2010 2:14 am
Actually, there are many “proofs” of P vs. NP all the time. There were  
two or three posted on math archives this month. The primary  
distinction between this one and the others seems to be social,
rather than technical. Namely, this one seems to have gotten the label  
of a “serious” effort,
without much technical distinguishability from many of the other  
similar claims.

My problem with this attempt is that
it is not clearly written. There should be an outline with a list of  
lemmas that together imply the
main result. Then we can try to verify or disprove the lemmas.  
Instead, we are spending time discussing what certain passages in the  
paper might mean, and only considering it invalid if there is no  
possible valid interpretation. The more ambiguous the text is, the  
more difficult this is. That’s
why it is usually incumbent on a mathematician to be as unambiguous as  
humanly possible.

People like Tao and Gowers can accomplish a lot in a few days, so I  
think if there’s no
meat here, it is a shame to waste those days. Especially since I don’t  
think either of their backgrounds matches this paper particularly  
well, and they don’t spend a lot of time on
computational complexity per se, so I’d like “our” share of their time  
to be very productive.
I’d be happy to be shown wrong, and
will be going through my copy of the paper just like everyone else,  
but I’m getting frustrated.

Harvey Friedman