[FOM] P NP buzz
Harvey Friedman
friedman at math.ohio-state.edu
Wed Aug 11 16:54:17 EDT 2010
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
More information about the FOM
mailing list