Slashdot Mirror
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."
It is indeed quite simple. Imagine a long string of operators like this (! is "not"):
(x1 or x4 or !x3) and (x1 and !x4 and x3) and (x2 or !x1 or !x4) etc.
The question is "Is there a way to assign true/false to all the variables such that the end result is true".
This is a satisfiability problem (SAT), and what makes it 3-SAT is that it has three variables per clause.
Sir –
I did some graduate research on satisfiability, so perhaps I can offer some illumination.
Satisfiability is a logic problem. Given a set of clauses that "or" a set of literals, which literals (and clauses) may be true or false, all "and"ed together, the question is: is there a set of literals (when true or false) that result in the overall statement being true. E.g.
X = (A or B) & (!A or !B) & (A or !B)
The question is: Is there a combination of A and B being true or false that would result in X being true? (In this example, X is true when A is true and B is false.)
3-SAT is satisfiability but with only 3-literals per clause e.g.
X = (A or B or C) and (A or !B or !C) and (!A or B or C) ...
There's a polynomial-time mapping from any satisfiability problem to 3-SAT, as there is between all NP complete problems, which mapping is why they are so-classified. In other words, if you solve one NP complete problem in polynomial time (namely big-O notation O(ax^n) where n is the complexity i.e. number of literals) you solve them all in polynomial time. The most famous of these NP complete problems is probably the Knapsack problem, though there are quite a few.
All to say, it's a logic puzzle that has quite a few applications but no simple solution yet.
I'm not sure if the above is in layman terms, but I hope it is somewhat helpful.
NP is short for Natalie Portman, and the car analogy follows:
Adleman's chief scientist, Nickolas Chelyapov, offered this illustration: Imagine that a fussy customer walks onto a million-car auto square and gives the dealer a complicated list of criteria for the car he wants.
"First," he says, "I want it to be either a Cadillac or a convertible or red." Second, "if it is a Cadillac, then it has to have four seats or a locking gas cap." Third, "If it is a convertible, it should not be a Cadillac or it should have two seats."
The customer rattles off a list of 24 such conditions, and the salesman has to find the one car in stock that meets all the requirements. (Adleman and his team chose a problem they knew had exactly one solution.) The salesman will have to run through the customer's entire list for each of the million cars in turn -- a hopeless task unless he can move and think at superhuman speed.
This serial method is the way a digital electronic computer solves such a problem.
You left out the most important part. It takes lots of work to find the car, but it takes a short time to check that it's the right car once it's found. In other words, if you're lucky and always guess the right car on your first try (in other words nondeterministically), you can check that it's the right solution quickly (in polynomial time). Nondeterministic polynomial time = NP.
In 3-SAT, it takes exponential of time to find the assignment to the variables that satisfies all the conditions, but it takes polynomial time to check whether a particular assignment is correct. It takes exponential time to factor a product of two large primes, but it takes polynomial time to make sure it's the correct factorization.
What a fool believes, he sees, no wise man has the power to reason away.
This is not a P=NP paper. The paper solves a problem of a related data structure in polynomial time (quartic time), then shows that it can be used to solve some cases of 3SAT. The 3 outputs the algorithm can give are "the formula is not satisfiable", "the formula is satisfiable" (and the solution is given), and "failure of classification" -- it couldn't solve the problem. The important question we wait for on the experts on this paper isn't "is it correct" (it probably is) but "how effective is it".
there's a 9 at the end
This is why your understanding fails. There is no end.
What is really so complicated by these simple examples:
1/3 + 1/3 + 1/3 = 3/3 = 1
And since 1/3 exactly equals 0.333... we have:
0.333... + 0.333... + 0.333... = 0.999...
And since the two sums are exactly equal, 0.999... equals 1. It's not really that magic, and your normal daily life will not be affected. It is, however, true.
c++;