Why do we think this is worthy of voting up? Is there any reason to think it might be correct?
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.
I think both Gowers and Tao talked about it. I don’t remember in how much depth.
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.
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.
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.
Words worth of a politician, but not a hacker!
Politicians are not.