P=NP proposed proof on Arxiv

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

P=NP proposed proof on Arxiv

Postby mike-l » Thu Jan 20, 2011 7:13 pm UTC

There's a paper on Arxiv which claims to prove P=NP by solving 3-SAT 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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
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

Postby scarecrovv » Thu Jan 20, 2011 9:40 pm UTC

I'm currently running the provided code. I'll let you all know what happens.

User avatar
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

Postby Yakk » Thu Jan 20, 2011 10:07 pm UTC

The paper says in the abstract "I tried it on lots of sample problems from 3-SAT, 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.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: P=NP proposed proof on Arxiv

Postby kmatzen » Thu Jan 20, 2011 10:23 pm UTC

I don't understand validating pure theory via experimentation.

Goplat
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: P=NP proposed proof on Arxiv

Postby Goplat » Thu Jan 20, 2011 10:34 pm UTC

Yakk wrote:The paper says in the abstract "I tried it on lots of sample problems from 3-SAT, and they all seemed fast".
It'll probably turn out to be O(n3 1.001n) or something like that... seems nice and polynomial, until n gets big enough :(

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: P=NP proposed proof on Arxiv

Postby letterX » Thu Jan 20, 2011 10:42 pm UTC

Goplat wrote:
Yakk wrote:The paper says in the abstract "I tried it on lots of sample problems from 3-SAT, and they all seemed fast".
It'll probably turn out to be O(n3 1.001n) or something like that... seems nice and polynomial, until n gets big enough :(

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 worst-case that bites you in the ass. And it can be very difficult to tell a-priori what the worst case for any given solver will be, before you actually hand it the problem and it suddenly takes forever.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: P=NP proposed proof on Arxiv

Postby achan1058 » Thu Jan 20, 2011 11:42 pm UTC

I haven't read the paper, but if what is said here is true, then why is something like this on the Arxiv?

User avatar
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

Postby Yakk » Fri Jan 21, 2011 12:03 am UTC

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.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: P=NP proposed proof on Arxiv

Postby kmatzen » Fri Jan 21, 2011 4:53 am UTC

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.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: P=NP proposed proof on Arxiv

Postby squareroot » Fri Jan 21, 2011 5:35 am UTC

keywords being "if you successfully proved it" :P A lot of people have already tried to solve this conjecture, apparently always with flaws more-or-less 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 - __ -

User avatar
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

Postby scarecrovv » Fri Jan 21, 2011 5:51 am UTC

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.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: P=NP proposed proof on Arxiv

Postby mike-l » Fri Jan 21, 2011 2:02 pm UTC

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.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests