P!=NP in the news

[R.D. Silverman]

Originally Posted by only_human

I was fascinated watching the developing evaluation of the paper. A preliminary consensus seems complete. Here is a blog that takes an optimistic view of this new form of peer review: http://cameronneylon.net/blog/p-%E2%...f-peer-review/ Perhaps blitz-read is a more apt term.

Among my peripatetic browsing about all of this I came across Leslie Valiant's theory of holographic algorithms which exponentially speed up some computations; this was very interesting to me. There is a (mod 7) operation that seems to be part of canceling a large part of the calculations -- leaving a simpler system to be counted (and that by some kind of weighing). It reminded me a bit of the AKS method so simplifying a row.

The proof is now being given a proper burial. The final nail in the coffin
comes from:

http://rjlipton.wordpress.com/2010/0...alikars-proof/


IMO there is nothing unusual about the peer review process that took place
for this paper EXCEPT that it took place in full view of the public. It is
quite typical for a proof of a dramatic result to be distributed by the author
to a number of expert peers for pre-publication criticism. However, this
is usually done privately. The only thing new about this paper is that the
reviews appeared on Internet blogs, instead of being done by private mail/email.

[only_human]

Originally Posted by R.D. Silverman

IMO there is nothing unusual about the peer review process that took place
for this paper EXCEPT that it took place in full view of the public. It is
quite typical for a proof of a dramatic result to be distributed by the author
to a number of expert peers for pre-publication criticism. However, this
is usually done privately. The only thing new about this paper is that the
reviews appeared on Internet blogs, instead of being done by private mail/email.

I felt that the character of the review was a bit different. For example, I don't think it would be likely for a stately private peer review process to include a substantial money offer to express an opinion that the paper is deeply flawed. Also there was a Google Docs collaborative paper that was moved to a wiki for documentation and collaboration of analysis. I think in a traditional review, the reviewers would try not to collaborate so as to not influence each other's analysis and expectations as a safeguard against unintentional bias.

[CRGreathouse]

Originally Posted by only_human

I felt that the character of the review was a bit different. For example, I don't think it would be likely for a stately private peer review process to include a substantial money offer to express an opinion that the paper is deeply flawed.

Scott wasn't a part of the reviewing, though. He made the offer mostly to discourage emails...

[only_human]

Originally Posted by CRGreathouse

Scott wasn't a part of the reviewing, though. He made the offer mostly to discourage emails...

True; I hope this kerfuffle didn't disrupt his vacation too much. On the other hand, in a sense, everyone who commented, in any way, became an ad-hoc part of the review process. I am amazed that some of the really wobbly wheels online didn't muscle their way into the discussion.

[R.D. Silverman]

Originally Posted by only_human

True; I hope this kerfuffle didn't disrupt his vacation too much. On the other hand, in a sense, everyone who commented, in any way, became an ad-hoc part of the review process. I am amazed that some of the really wobbly wheels online didn't muscle their way into the discussion.

Some of them did (e.g. a number of ignorant people make comments about
how NP stood for "non polynomial")

[Primeinator]

Originally Posted by R.D. Silverman

The proof is now being given a proper burial. The final nail in the coffin
comes from:

http://rjlipton.wordpress.com/2010/0...alikars-proof/

Too bad! It would have been nice to see this problem solved.

[ixfd64]

Oh well. At least he tried.

[davieddy]

Excerpt from my great Oxford friend Paul Seymour:

"Did you hear that there might be a proof that P != NP? It looks very plausible (ie long and unintelligible, but sounding as though the person writing it was an expert). Better than a proof that P=NP I guess, that would have made much of my mathematical life pointless."

David

(Google as necessary)

[Batalov]

...well at least now his life is still pointful.

[Primeinator]

Originally Posted by davieddy

Excerpt from my great Oxford friend Paul Seymour:

"Did you hear that there might be a proof that P != NP? It looks very plausible (ie long and unintelligible, but sounding as though the person writing it was an expert). Better than a proof that P=NP I guess, that would have made much of my mathematical life pointless."

David

Is it general consensus that P and NP are not equal?

[xilman]

Originally Posted by Primeinator

Is it general consensus that P and NP are not equal?

AFAIK, the general consensus is that it unlikely that P and NP are not equal. However, the general consensus has been wrong on numerous occasions in the past.

FWIW, my guess is that P !=NP but that there is a fair chance that integer factorization is in P.


Paul