Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT ProblemThis algorithm claims to have solved the 3-SAT NP-complete problem in polynomial time. I've confirmed that it can solve a 47 variable problem on my machine in 2.7 minutes, but as of yet have nothing to compare this result against.
This is particularly interesting since just a few months ago, someone tried to prove P!=NP. If this algorithm actually behaves the way its supposed to, it would instantly prove that P=NP and render the vast majority of cryptography obsolete, along with lots of other
crazy implications.
This is because all problems in NP must be reducible to a problem in NP-complete in polynomial time: "But if
any single problem in NP-complete can be solved quickly, then
every problem in NP can also be quickly solved" -
link. So, in theory, given this polynomial time algorithm for SAT-3, you can reduce any other NP complete problem, like the traveling salesman, into the SAT-3 problem in polynomial time, then apply this algorithm to solve it. If, that is, this algorithm actually holds up. Seeing as this directly contradicts an earlier attempt to prove that this was, in fact, impossible, it remains to be seen what will happen.
But if this proves that P=NP, then
****s gonna get real.