P!=NP in the news
 

Stolen from a story at SlashDot.
[URL="http://www.scribd.com/doc/35539144/pnp12pt"]http://www.scribd.com/doc/35539144/pnp12pt[/URL]

From a blog post: [URL="http://gregbaker.ca/blog/2010/08/07/p-n-np/"]http://gregbaker.ca/blog/2010/08/07/p-n-np/[/URL]

That's all I know.

[QUOTE=willmore;224488]Stolen from a story at SlashDot.
[URL="http://www.scribd.com/doc/35539144/pnp12pt"]http://www.scribd.com/doc/35539144/pnp12pt[/URL]

From a blog post: [URL="http://gregbaker.ca/blog/2010/08/07/p-n-np/"]http://gregbaker.ca/blog/2010/08/07/p-n-np/[/URL]

That's all I know.[/QUOTE]

The wording of the announcement makes it clear that this is
not the effort of a professional. (too much hyperbole and
informality) It is very unlikely to be correct.

I don't know. Although I would be surprised if the problem was resolved by this attempt, the paper looks reasonable, and Deolalikar has been active in the field for some time.

It passed all the standard not-a-crank tests easily: no positive [url=http://primes.utm.edu/notes/crackpot.html]crackpot index[/url], typeset in TeX, 60+ citations including the relevant ones (e.g., Razborov & Rudich), no obvious mistakes in the first dozen pages (not my field -- just nothing glaringly wrong).

It also passes the [url=http://scottaaronson.com/blog/?p=304]Ten Signs a Claimed Mathematical Breakthrough is Wrong[/url] test. I'd like to hear an expert chime in on #5 and #3 when they finish reading, just as a sanity check. (This does *not* speak to the correctness of the final result, just its seriousness.)

Also, Stephen Cook says it looks like a serious attempt, and that's not nothing.

[QUOTE]The wording of the announcement makes it clear that this is
not the effort of a professional.[/QUOTE]I completely disagree. The "announcement" comes from a private email apparently sent to experts in the field, to get their feedback on his paper. And the researcher is not an unknown crank.

Scott AAronson's blog, [URL]http://www.scottaaronson.com/blog/[/URL] , says that while the paper introduces some thought provoking ideas, the only mechanism that occurs to him to fairly convey his hunch about the paper without being unfair to the author and without interrupting his vacation in Israel and Greece to do the hard work to back up his hunch is to offer a personal $200,000 supplement to the Clay Millennium Prize if the paper is right.

He says "I'm dead serious -- I can afford it about as well as you think I can"

[QUOTE=only_human;224526]Scott AAronson's blog, [URL]http://www.scottaaronson.com/blog/[/URL] , says that while the paper introduces some thought provoking ideas, the only mechanism that occurs to him to fairly convey his hunch about the paper without being unfair to the author and without interrupting his vacation in Israel and Greece to do the hard work to back up his hunch is to offer a personal $200,000 supplement to the Clay Millennium Prize if the paper is right.

He says "I'm dead serious -- I can afford it about as well as you think I can"[/QUOTE]

I took a quick glance at the paper. It is a very serious effort.
The author pulls together some ideas from finite model theory and
the theory of random graphs (specifically, large random instances
of the Satisfiability problem) to show that large random instances
of SAT are not be solvable in P-time.

I intend to read this in detail. However, some of the aspects of the paper
are new to me as are some of the prior results used by the paper.
Reading it will take a MAJOR effort. (as well as reading some of the
referenced papers)

Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?

[QUOTE=Primeinator;224598]Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?[/QUOTE]

Maybe 6-36 months for consensus to appear, sure. But if the paper is wrong it often comes out in a week or two. :smile:

[QUOTE=CRGreathouse;224606]Maybe 6-36 months for consensus to appear, sure. But if the paper is wrong it often comes out in a week or two. :smile:[/QUOTE]

I have started reading it in details. The general approach is very creative
and [b]seems[/b] to be workable.

The comments at [url]http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/[/url] seem to be the most cogent of the places that I've looked. These, and a comment I've seen on Scott's blog seem to be focusing in on section 7.2.1 of the paper as potentially problematic. I've seen 3 versions of the paper floating around: a 8pt font one that is 66 pages long, a 12pt 102 page version dated Aug 6, and a 103 page version dated Aug 8. They all seem to have the same content. The Aug 8 version prepends a dedication.

paper have been updated
[URL]http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf[/URL]