mersenneforum.org P!=NP in the news
 Register FAQ Search Today's Posts Mark Forums Read

 2010-08-08, 23:00 #1 willmore     Aug 2002 6010 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/p-n-np/ That's all I know.
2010-08-09, 00:43   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by willmore Stolen from a story at SlashDot. http://www.scribd.com/doc/35539144/pnp12pt From a blog post: http://gregbaker.ca/blog/2010/08/07/p-n-np/ That's all I know.
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.

 2010-08-09, 01:02 #3 CRGreathouse     Aug 2006 3×1,993 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 not-a-crank 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.
2010-08-09, 03:48   #4
Zeta-Flux

May 2003

7·13·17 Posts

Quote:
 The wording of the announcement makes it clear that this is not the effort of a professional.
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.

 2010-08-09, 07:18 #5 only_human     "Gang aft agley" Sep 2002 1110101010102 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 2010-08-09 at 07:26 Reason: accidently expanded a contraction in the quote. now fixed 2010-08-09, 13:16 #6 R.D. Silverman Nov 2003 22·5·373 Posts Quote:  Originally Posted by only_human 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"
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)

 2010-08-09, 17:05 #7 Primeinator     "Kyle" Feb 2005 Somewhere near M52.. 3·5·61 Posts Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?
2010-08-09, 17:26   #8
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by Primeinator Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?
Maybe 6-36 months for consensus to appear, sure. But if the paper is wrong it often comes out in a week or two.

2010-08-09, 18:47   #9
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by CRGreathouse Maybe 6-36 months for consensus to appear, sure. But if the paper is wrong it often comes out in a week or two.
I have started reading it in details. The general approach is very creative
and seems to be workable.

 2010-08-09, 19:21 #10 only_human     "Gang aft agley" Sep 2002 EAA16 Posts The comments at http://rjlipton.wordpress.com/2010/0...t-equal-to-np/ 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.
 2010-08-09, 21:28 #11 firejuggler     "Vincent" Apr 2010 Over the rainbow 275810 Posts paper have been updated http://www.hpl.hp.com/personal/Vinay...np_updated.pdf

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 303 2021-10-01 20:47 gd_barnes No Prime Left Behind 253 2021-08-15 05:26 Cruelty Riesel Prime Search 41 2010-03-08 18:46 NBtarheel_33 Hardware 17 2009-05-04 15:52 KEP Riesel Base 3 Attack 4 2008-12-17 11:54

All times are UTC. The time now is 16:57.

Fri Jan 28 16:57:05 UTC 2022 up 189 days, 11:26, 1 user, load averages: 1.36, 1.62, 1.53