mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2010-08-08, 23:00   #1
willmore
 
willmore's Avatar
 
Aug 2002

6010 Posts
Default 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.
willmore is offline   Reply With Quote
Old 2010-08-09, 00:43   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by willmore View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-08-09, 01:02   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16EC16 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2010-08-09, 03:48   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

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.
Zeta-Flux is offline   Reply With Quote
Old 2010-08-09, 07:18   #5
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

2×1,877 Posts
Default

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
only_human is offline   Reply With Quote
Old 2010-08-09, 13:16   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by only_human View Post
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)
R.D. Silverman is offline   Reply With Quote
Old 2010-08-09, 17:05   #7
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

2·3·149 Posts
Default

Generally speaking, doesn't it take several years for a newly proposed mathematical proof to be accepted?
Primeinator is offline   Reply With Quote
Old 2010-08-09, 17:26   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111011002 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-08-09, 18:47   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-08-09, 19:21   #10
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

72528 Posts
Default

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.
only_human is offline   Reply With Quote
Old 2010-08-09, 21:28   #11
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2×3×5×79 Posts
Default

paper have been updated
http://www.hpl.hp.com/personal/Vinay...np_updated.pdf
firejuggler is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
News gd_barnes No Prime Left Behind 250 2020-06-29 13:23
News gd_barnes Conjectures 'R Us 281 2020-02-26 21:25
Other news Cruelty Riesel Prime Search 41 2010-03-08 18:46
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
News KEP Riesel Base 3 Attack 4 2008-12-17 11:54

All times are UTC. The time now is 19:14.

Tue Aug 11 19:14:08 UTC 2020 up 25 days, 15 hrs, 2 users, load averages: 1.37, 1.62, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.