Author Topic: Polynomial time algorithm for NP-complete problem  (Read 2109 times)

0 Members and 1 Guest are viewing this topic.

Offline blackhole

  • Still not over the rainbow
  • 29
  • Destiny can suck it
    • Black Sphere Studios
Polynomial time algorithm for NP-complete problem
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.

 

Offline Ghostavo

  • 210
  • Let it be glue!
    • Skype
    • Steam
    • Twitter
Re: Polynomial time algorithm for NP-complete problem
**** yeah!
"Closing the Box" - a campaign in the making :nervous:

Shrike is a dirty dirty admin, he's the destroyer of souls... oh god, let it be glue...

 

Offline Topgun

  • 210
Re: Polynomial time algorithm for NP-complete problem
Or it could mean that somehow 3-SAT is not NP-complete. That seems unlikely though.

 

Offline blackhole

  • Still not over the rainbow
  • 29
  • Destiny can suck it
    • Black Sphere Studios
Re: Polynomial time algorithm for NP-complete problem
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.

 

Offline General Battuta

  • Poe's Law In Action
  • 214
  • i wonder when my postcount will exceed my iq
Re: Polynomial time algorithm for NP-complete problem
Reading discussion it sounds like this is not going to hold up.

 

Offline Ghostavo

  • 210
  • Let it be glue!
    • Skype
    • Steam
    • Twitter
Re: Polynomial time algorithm for NP-complete problem
Well, is this, as they say, it?
"Closing the Box" - a campaign in the making :nervous:

Shrike is a dirty dirty admin, he's the destroyer of souls... oh god, let it be glue...