News for hackers. Stuff that matters.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by jey on Wednesday January 19, 2011 @06:33PM (#2121761)
Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by tzs on Wednesday January 19, 2011 @06:47PM (#2121822)
Failure can be interesting. Consider the attempt a few months ago by Deolalikar. The ensuing public discussion, which including many big names in complexity theory and at least one Fields medallist, was very enlightening.

This particular attempt involves someone claiming P=NP, and they have code. Even people who aren't complexity theorists can jump in on this one, by analyzing the code to verify it really is in P, and by trying to find problem instances it fails on.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by celoyd on Wednesday January 19, 2011 @07:04PM (#2121879)
at least one Fields medallist

I think both Gowers and Tao talked about it. I don’t remember in how much depth.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by cyrus_ on Wednesday January 19, 2011 @07:01PM (#2121870)
It looks like the paper is fairly straightforward. It purports to give a polynomial time algorithm for 3-SAT.

Interesting facts:

- It is a O(n^4m) algorithm, where n is the number of boolean variables and m is the number of disjunctions.

- It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values.

- The author claims to have implemented and tested the algorithm on reasonably sized problems, though I don't see his code posted anywhere (?). Someone else appears to have implemented it here: https://github.com/anjlab/sat3.

- The author references no prior work, just review papers on the problem itself.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by wnoise on Wednesday January 19, 2011 @09:53PM (#2122409)
> - It not only tells you whether the formula is satisfiable or not, but gives you the satisfying values.

Any yes/no NP solver can be turned into one that does this with polynomial overhead. After finding there is a solution, you ask it the similar problem "does this have solution with the first bit set to true?", then "does this have a solution with the first bit set to <answer to previous question> and the second bit set to true?", and so forth until you've identified all bits.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by azakai on Wednesday January 19, 2011 @06:49PM (#2121828)
It is almost certainly not correct, simply because so many have tried, and none succeeded.

However, this guy seems very cool - he is humble about his work, appears very serious, and even puts his code on github. And even if wrong, his approach might be interesting.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by vilda on Wednesday January 19, 2011 @08:21PM (#2122119)
"because so many have tried, and none succeeded"

Words worth of a politician, but not a hacker!

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by tomjen3 on Thursday January 20, 2011 @01:48AM (#2122921)
No words worthy of a Hacker - we are bound by reality.

Politicians are not.

Re:The polynomial algorithm for 3-SAT problem (or P=NP) by mikemol on Thursday January 20, 2011 @01:23PM (#2124638)
Our actions are bound by reality. Our choices are bound by what we posit reality to be.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by monochromatic on Wednesday January 19, 2011 @06:38PM (#2121782)
It's on the arXive, so you know it's legit.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by jey on Wednesday January 19, 2011 @06:45PM (#2121806)
Sarcasm, right? The arXiv has very little quality control (intentionally).
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by roel_v on Thursday January 20, 2011 @04:26AM (#2123156)
I think the point was that quite a bit of what is on arXiv is from quacks and nutcases. (maybe not the majority, or even a large part - but enough to cast some shadow over arXiv itself, and therefore over other submissions as well).
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by zitterbewegung on Wednesday January 19, 2011 @06:46PM (#2121815)
Just because its on arXiv doesn't mean its legitimate. Its more likely that it is legitimate if it gets published (with a few exceptions like the Poincaré conjecture.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by nandemo on Wednesday January 19, 2011 @10:26PM (#2122506)
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by JadeNB on Friday January 21, 2011 @12:45AM (#2126583)
Yeah, like that will work.
Re:The polynomial algorithm for 3-SAT problem (or P=NP) by lwat on Wednesday January 19, 2011 @06:51PM (#2121836)
We just want to know what the flaw in his reasoning is.