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."
Even though this is probably wrong, just based on the sheer number of prior failures ...
Okay, so I'm going to agree with you that it's probably wrong. After reading the paper once last night in a sort of sleepy state, it's certainly a novel way of massaging each 3-Sat problem into an expanded space of memory (compact triplets structures) and then reducing this to solve the problem (all within polynomial time).
So the great thing about this paper is that it's short, it's not theoretical (which is a double-edged sword)/has been implemented (in Java, no less) and it's incredibly falsifiable. I'm not intelligent enough to poke holes in his proofs for this work but people can apply the code to DIMACS formatted problems to their heart's content and if they find one that produces the wrong answer then this is falsified.
I hope we find someone capable of commenting on the proof involving the transformation of the problem from compact triplets formula to compact triplets structure and the hyperstructures presented in the paper. If this is legit, the 3-Sat problem is one that more complex problems are reduced to in order to show that said complex problems are NP-complete. And that's something that's been proved by the Cook-Levin theorem and given in the classic Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson.
Refreshingly tangible implementation, if I may say so myself!
My work here is dung.
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.
I have code for a solution to the Goldbach Conjecture, but it doesn't fit into my free storage on github....
what does P stand for?
Portman.
Oh wait, sorry, I was answering the comment above yours...
coding is life
Absolutely untrue. All experts in the field that I've spoken to think that P is probably not equal to NP, but that a proof either way is going to be very hard.
Absolutely correct. The difference between say, computer science and sociology, is that computer scientists require absolute proofs. In other words, if you claim that P==NP, as this paper does, then I require you to show that it is so for all possible inputs.
The paper, in fact, does not show such a thing. To the contrary, it fails to show a sound and complete reduction of 3-SAT to hyperstructures, or CTF or CTS or whatever other acronyms were made up by the author. I'm not saying that he's wrong, simply that this is not a proof - it is only a claim. The author claims to have "proven" his algorithm is polynomial time by giving it a smattering of inputs and noting that the time the algorithm took to complete increased by a polynomial factor of the input size.
Clearly the author has not studied his algorithmic complexity texts well enough to understand the definition of Big-O. Big-O only claims that algorithmic growth is asymptotic to a given curve as the input size goes to infinity from some value n0. In other words, many algorithms may display linear growth to a point, and then become exponential after input size greater than n0. A statistical analysis will not prove anything. The author needs to do a full algorithmic analysis instead.
I predict this paper will be rapidly debunked and we will still not know if P==NP.
Government is not reason; it is not eloquent; it is force. Like fire, it is a dangerous servant and a fearful master.
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.
And if each car is located in a different city, then he'll have to go travelling in order to test all the criteria. Of course, he wouldn't want to end up hitting the same city twice...
WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS
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++;
If you're so good at it, at least translate the line for us!
smartass...
Welcome to the club. My friends and colleagues routinely think of me as "one of the smartest people they know" (or so I've been told). Articles like this remind me of my true status, which is helpful in not getting cocky.
God invented whiskey so the Irish would not rule the world.