There's a paper on Arxiv which claims to prove P=NP by solving 3SAT in polynomial time. It passes initial crank tests, and made Slashdot if that means anything. Probably wrong, but looks many orders of magnitude better than most proposed 'proofs'. He's also released source code, which I think gives him much credit as it makes his claims easily falsifyable.
I started to read through it but it's really not my area of expertise. One thing that concerns me, and might be addressed as I've only spent 30 minutes glancing at it while in a meeting, is that his structure seems to span over all n! combinations of the n literals, so it's unclear how that is going to result in doing anything in polynomial time. I'll probably look deeper into it later, but there are probably plenty of people who know more about the topic than me hanging out in this forum.
P=NP proposed proof on Arxiv
Moderators: phlip, Moderators General, Prelates
P=NP proposed proof on Arxiv
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
 scarecrovv
 It's pronounced 'double u'
 Posts: 674
 Joined: Wed Jul 30, 2008 4:09 pm UTC
 Location: California
Re: P=NP proposed proof on Arxiv
I'm currently running the provided code. I'll let you all know what happens.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P=NP proposed proof on Arxiv
The paper says in the abstract "I tried it on lots of sample problems from 3SAT, and they all seemed fast".
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: P=NP proposed proof on Arxiv
I don't understand validating pure theory via experimentation.
Re: P=NP proposed proof on Arxiv
It'll probably turn out to be O(n^{3} 1.001^{n}) or something like that... seems nice and polynomial, until n gets big enoughYakk wrote:The paper says in the abstract "I tried it on lots of sample problems from 3SAT, and they all seemed fast".
Re: P=NP proposed proof on Arxiv
Goplat wrote:It'll probably turn out to be O(n^{3} 1.001^{n}) or something like that... seems nice and polynomial, until n gets big enoughYakk wrote:The paper says in the abstract "I tried it on lots of sample problems from 3SAT, and they all seemed fast".
Or even more simply: the vast majority of SAT instances are actually pretty easy. There's lots of researchers working on SAT solvers, and they do a very good job of solving very large problems very quickly. Its the worstcase that bites you in the ass. And it can be very difficult to tell apriori what the worst case for any given solver will be, before you actually hand it the problem and it suddenly takes forever.
Re: P=NP proposed proof on Arxiv
I haven't read the paper, but if what is said here is true, then why is something like this on the Arxiv?
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P=NP proposed proof on Arxiv
kmatzen wrote:I don't understand validating pure theory via experimentation.
Experimental mathematics is quite useful.
Suppose you have what you think is a good solution  this is the first step you should do, test it on random samples.
The next step is to try it on what other solutions find "hard".
These are all easier than proving your solution correct quite often. And sometimes, you find a counter example to what you think is true.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: P=NP proposed proof on Arxiv
Yakk wrote:kmatzen wrote:I don't understand validating pure theory via experimentation.
Experimental mathematics is quite useful.
Suppose you have what you think is a good solution  this is the first step you should do, test it on random samples.
The next step is to try it on what other solutions find "hard".
These are all easier than proving your solution correct quite often. And sometimes, you find a counter example to what you think is true.
Sorry, I read the topic of the post, jumped to the paper, saw that they were doing experimental validation and I thought they were somehow using that to claim P = NP since it worked most of the time. Sure, it makes sense to at least test your ideas before wasting time, but it's not a substitute for a proof and if you provide the proof, then why provide the experimental validation? You either proved it or you didn't prove it. The experiment can't strengthen the argument if you sufficiently proved it.

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: P=NP proposed proof on Arxiv
keywords being "if you successfully proved it" A lot of people have already tried to solve this conjecture, apparently always with flaws moreorless embedded in the logic. And if you can provide some evidence that, "hey, this actually seems to work!" then it make other people give the paper more credence until the proposed proof is resolved one way or the other.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
 scarecrovv
 It's pronounced 'double u'
 Posts: 674
 Joined: Wed Jul 30, 2008 4:09 pm UTC
 Location: California
Re: P=NP proposed proof on Arxiv
The code ran, and it appeared to finish whatever it was doing, but then it looks like it tried and failed to open a window (presumably to show a pretty graph), and died. It also left a corrupt png, which I guess it was in the process of creating when it couldn't open the window. I don't feel motivated to fix it, so I guess I'll leave it to others. If this turns out to be correct, I'll hear about it.
Re: P=NP proposed proof on Arxiv
achan1058 wrote:I haven't read the paper, but if what is said here is true, then why is something like this on the Arxiv?
Because Arxiv has open submissions?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Who is online
Users browsing this forum: No registered users and 6 guests