20100808, 23:00  #1 
Aug 2002
61 Posts 
P!=NP in the news
Stolen from a story at SlashDot.
http://www.scribd.com/doc/35539144/pnp12pt From a blog post: http://gregbaker.ca/blog/2010/08/07/pnnp/ That's all I know. 
20100809, 00:43  #2  
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 
Quote:
not the effort of a professional. (too much hyperbole and informality) It is very unlikely to be correct. 

20100809, 01:02  #3 
Aug 2006
5987_{10} Posts 
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 notacrank tests easily: no positive crackpot index, 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 Ten Signs a Claimed Mathematical Breakthrough is Wrong 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. 
20100809, 03:48  #4  
May 2003
7×13×17 Posts 
Quote:


20100809, 07:18  #5 
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Scott AAronson's blog, http://www.scottaaronson.com/blog/ , 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" Last fiddled with by only_human on 20100809 at 07:26 Reason: accidently expanded a contraction in the quote. now fixed 
20100809, 13:16  #6  
"Bob Silverman"
Nov 2003
North of Boston
2×3^{3}×139 Posts 
Quote:
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 Ptime. 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) 

20100809, 17:05  #7 
"Kyle"
Feb 2005
Somewhere near M52..
7·131 Posts 
Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?

20100809, 17:26  #8 
Aug 2006
1011101100011_{2} Posts 

20100809, 18:47  #9 
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 

20100809, 19:21  #10 
"Gang aft agley"
Sep 2002
2·1,877 Posts 
The comments at http://rjlipton.wordpress.com/2010/0...tequaltonp/ 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.

20100809, 21:28  #11 
"Vincent"
Apr 2010
Over the rainbow
2^{2}×7×103 Posts 
paper have been updated
http://www.hpl.hp.com/personal/Vinay...np_updated.pdf 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
News  gd_barnes  Conjectures 'R Us  305  20230121 13:53 
News  gd_barnes  No Prime Left Behind  258  20230121 11:09 
Other news  Cruelty  Riesel Prime Search  41  20100308 18:46 
The news giveth, the news taketh away...  NBtarheel_33  Hardware  17  20090504 15:52 
News  KEP  Riesel Base 3 Attack  4  20081217 11:54 