[blackhole]

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.

[Ghostavo]

**** yeah!

[Topgun]

Or it could mean that somehow 3-SAT is not NP-complete. That seems unlikely though.

[blackhole]

Well a lot of specific instances of 3-SAT are actually very easy to compute, so the real test is if the algorithm can preform in polynomial time on the really hard 3-SAT problems.

[General Battuta]

Reading discussion it sounds like this is not going to hold up.

[Ghostavo]

Well, is this, as they say, it?