Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT Problem
This 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