(This is likely my last post on the alleged P NE NP paper unless
more real news on it occurs. The only real news I can see happening
at this point is a retraction.)
I have not commented much on the alleged P ≠ NP
since I was waiting for better informed or more opinionated
people to comment first. Now that the dust has somewhat settled
here is are some views of points of view and some pointers to points of interest.

The best place to read about the technical details of
the problems with the proof is Lipton's Blog Entries:
here,
here,
here,
here,
here,
and
here.
Also the Wikipedia entry
here.

Some people are saying that
Scott's post
was nasty. Here is an excerpt from Scott's post:
What's obvious from even a superficial reading is that Deolalikar's
manuscript is wellwritten, and that it discusses the history,
background, and difficulties of the P vs. NP question in a competent way.
More importantly (and in contrast to 98% of claimed P ≠ NP proofs),
even if this attempt fails, it seems to introduce some
thoughtprovoking new ideas, particularly a connection
between statistical physics and the firstorder logic
characterization of NP. I'll leave it to the commenters
to debate whether Deolalikar's paper exhibits one or more of the
Ten Signs A Claimed Mathematical Breakthrough Is Wrong.
Scott, that is downright nasty!
Calling a paper wellwritten!! Accusing it of having
thoughtprovoking new ideas!! Scott, you are just one Nasty dude!!
More seriously, Scotts offer of $200,000 if the proof is correct
(more formally, if he wins the Mil prize) was considered nasty by some.
Being skeptical and quantifing your skepticism is not nasty.
Other posts worth looking at:

Written preDeo, Lance now looks like Nostradamus:
So you think you've settled P vs NP.
(NOTE personal triumph I got the spelling of Nostradamus right on my first try!)

A preDeo post of Scott's on
10 signs a claimed mathematical
breakthrough is wrong. Deolalikar passed most of these.

A postDeo post of Scott's that was likely inspired by Deo:
8 signs your proof of P ≠ NP is wrong.
One of Scott's signs cuts both ways he says that the use of Descriptive Complexity Theory is one of
the signs.
He claims (correctly)
... subtle differences in encoding can lead to HUGE differences in computational complexity.
Indeed, this was one of the problems with the DeoProof. However, I think Descriptive complexity theory
is one of the few techniques that has not been proven cannot work. So I take its use as
a good sign.

Lance was on vacation when all of this happened so
he posted on it when he got back. He was skeptical from the beginning and he says why.
(See
here.)
People respond by saying that the paper inspired a lot of interesting discussion, and
hence... I'm not sure Lance shouldn't be skeptical? Lance shouldn't say he is skeptical?
Lance should phrase his skepticism more politely?
I'm not sure what the objection to his post really is.

Is the proof correct? It looks like there are enough serious
flaws that the answer for now is no. By now this is old news.

I was originally skeptical (see
here) since there has been no progress on P vs NP at all so its surprising that there is this
much progress so fast.
I do not know if this is valid reasoning. Has any serious hard math problem been solved
all of a sudden after no progress on it?
Has there truly been no progress? We might not know until we solve it in 3000 AD and look back
and see which results from 19702010 ended up being relevant.

Deolalikar should, by Thursday Aug 26, 2010 (the first day of Barriers II)
either (1) retract the claim, or (2) post a version that fixes ALL of
the flaws found and explains the fixes. If he does neither of these two
things then he will cease to be a serious researcher.

It would be impossible to have a version that fixes ALL of the flaws
by Thursday Aug 26, 2010. Hence he needs to retract by then.
(Some would say sooner. Much sooner. Like... now.)

Was all of this good for the community? It got some talking and the people
who read the proof learned some complexity. If this gets more people
interested in the problem, that's got to be a good thing.
If some interesting ideas come out of this, even indirectly (e.g., Terry Tao
is inspired to read up on finite model theory and comes up with a result of interest)
then it will of course be a good thing.
However, if more of these proofs come out and the community spends
too much time on them, that will be bad.

Why did people take this paper so seriously?

It was in LaTeX!

It was long!

It was by a respectable researcher. (More on that later.)

It used familiar notation.

It seemed to have some good ideas in. It may still. (More on that later.)

It was on Slashdot and on Lipton's blog. But this begs the question:
why was it on slashdot and why did Lipton take it seriously?
Dick I am not asking this rhetorically if you read this please leave a comment
about why you took it seriously. I am not asking this sarcastically or in any
other nasty way. (I know YOU won't think so but other readers might.)

Others took it seriously. Chicken and egg problem here.

It had very few of the usual trademarks of papers written by cranks.

It was a proof in the correct direction (a proof that P=NP would be taken
less seriously, though the result, if true, would be more awesome!!!)

In the age of the web, news travels fast (I know of 3 other serious people claiming
to have shown P ≠ NP; however, that was preweb so they were debunked
before it got very far. I'm not quite sure which ones went public so I decline to
mention their names.)

How respectable a researcher is Deolalikar?
I do not know any other work that he is done.
He is not someone
you've heard about as having done
excellent work. The fact that some in the community took his work
seriously is an excellent sign that our community is not
elitist. They took it seriously based on its merits.
(The fact that some did not take it seriously is irrelevant.)

Are there interesting ideas in it? The answer from the latest comments
by knowledgeable people on Lipton's blogs seems to be no. Oh well.

In the midst of all of this came the DUMBEST comment on a post of mine EVER!!
In a recent
post
I noted that a recent (2007) article on number theory still referred to factoring
as being easy. I meant to imply that this was bad they should at least acknowledge
the issues involved even if they don't care. One of the comments was
Since when do mathematicians care about the notion of polynomial time?
Note that this is the same week when Gowers and Tao, two Fields Medal winners, are
carefully looking over an alleged proof that P ≠ NP.
Other mathematicians were looking at it also.
The notion that mathematicians do not care about polynomial time is
just so 1990's.

Posted By GASARCH to
Computational Complexity at 8/17/2010 08:47:00 AM