Hard Light Productions Forums

Off-Topic Discussion => Programming => Topic started by: blackhole on January 19, 2011, 06:40:28 pm

Title: Polynomial time algorithm for NP-complete problem
Post by: blackhole on January 19, 2011, 06:40:28 pm
Reference Implementation of Romanov's Polynomial Algorithm for Boolean 3-SAT Problem (https://github.com/anjlab/sat3)

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 (http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof).

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 (http://en.wikipedia.org/wiki/NP-complete#Formal_overview). 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 (http://xkcd.com/849/).
Title: Re: Polynomial time algorithm for NP-complete problem
Post by: Ghostavo on January 19, 2011, 06:44:20 pm
**** yeah!
Title: Re: Polynomial time algorithm for NP-complete problem
Post by: Topgun on January 19, 2011, 06:46:42 pm
Or it could mean that somehow 3-SAT is not NP-complete. That seems unlikely though.
Title: Re: Polynomial time algorithm for NP-complete problem
Post by: blackhole on January 19, 2011, 06:52:19 pm
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.
Title: Re: Polynomial time algorithm for NP-complete problem
Post by: General Battuta on January 20, 2011, 02:36:02 pm
Reading discussion it sounds like this is not going to hold up.
Title: Re: Polynomial time algorithm for NP-complete problem
Post by: Ghostavo on January 23, 2011, 07:11:40 pm
Well, is this, as they say, it?