Follow Slashdot blog updates by subscribing to our blog RSS feed

 



Forgot your password?
typodupeerror
Note: You can take 10% off all Slashdot Deals with coupon code "slashdot10off." ×
Science

Submission + - Polynomial Time Code for 3-SAT Released, P==NP->

An anonymous reader writes: Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical.
Link to Original Source
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

Polynomial Time Code for 3-SAT Released, P==NP

Comments Filter:

The test of intelligent tinkering is to save all the parts. -- Aldo Leopold

Working...