P=NP proposed proof on Arxiv

[mike-l]

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.

[scarecrovv]

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

[Yakk]

The paper says in the abstract "I tried it on lots of sample problems from 3-SAT, and they all seemed fast".

[kmatzen]

I don't understand validating pure theory via experimentation.

[Goplat]

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(n³ 1.001ⁿ) or something like that... seems nice and polynomial, until n gets big enough

[letterX]

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(n³ 1.001ⁿ) 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]

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

[Yakk]

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.

[kmatzen]

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]

keywords being "if you successfully proved it" 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.

[scarecrovv]

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]

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?