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."
for the jews
check my dubs --->
Damn you math geeks. Why must you come here and spew your incomprehensible formulas.
Do not meddle in the affairs of sysadmins, for they are subtle, and quick to anger.
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.
I tried to look the problem up on Wikipedia, and all I got was inscrutable high-level math. From what I can gather, I seems like something that could be explained in layman's terms. Would someone be kind enough to do so?
P=NP IFF N is equal to 1.
QED
Next problem?
Your hair look like poop, Bob! - Wanker.
Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical.
No, it means good encryption will be much less practical. Computers will always get faster so "too slow" is not a good argument. If P != NP you can always make encryption too hard to break by increasing the key size - the cost to encrypt and decrypt only goes up polynomial with key size but cost to break it goes up exponentially, which makes it too hard even for those with supercomputers. If P = NP it means the cost to break it only goes up polynomially. This put the cost to encrypt in the same realm as the cost to break. So you can use much bigger keys but it becomes more expensive and may stop petty criminals but won't stop people with supercomputers.
"Damn you math geeks. Why must you come here and spew your incomprehensible formulas." - by alta (1263) on Thursday January 20, @11:40AM (#34940832) Homepage
Heh, it is HARD, but not "incomprehensible": See, I recall those "P=NP" set theory type problems in DISCRETE MATH (part of CSC degree requirements alongside Calc - which the FUNNY PART is, I have yet to use that (@ least in Database/Information Systems type programming))...
While initially learning it, I also recall thinking to myself:
"DAMN, this stuff is tough!"
Mainly because in that type of "math" (discrete seemed to me a "mishmash" of MANY concepts like this one, logic, & more) you have to THINK/CONCENTRATE, like mad, & your answers are many times only CLOSE approximations as well.
APK
P.S.=> If you've ever seen the film "21" (about Johnny Chan, the poker player, from what I understand)? They're largely applying that portion of DISCRETE MATH in it (calculating the odds of an occurrence from a subset of possibles)... apk
To give a nice simple explanation ...
You have a bunch of interesting problems, which currently can only be run in exponential time - making them infeasable.
The thing is, there is no proof that they are only exponential - AND every problem in this set can be converted to all other problems in that set.
So the first person to solve one in Polynomial time solves all of them - and pretty much changes the world - including making encryption useless, and other things very effective - such as bin packing, travelling through a number of nodes (TSP) and other things.
8=====D
Has anyone figured out a proof that the backtracking is limited in some way that creates a polynomial bound? There are ample examples of problems where some backtracking occurs, and I'm wondering if it isn't possible to construct a problem class where it actually ends up going over a larger than polynomial portion of the search space.
Reading the submission in front was like trying to write ancient Greek in MS OFFICE! The summary made my ache and I felt like I was caught inside a 4/3 pi r cubed loop statement!
Did anybody check the software offered really does what it's supposed to do and not install something not so funny on your machine?
I have code for a solution to the Goldbach Conjecture, but it doesn't fit into my free storage on github....
Couldn't the existence of this working polynomial-time algorithm mean that the previous work which showed the 3-SAT problem to be NP-Complete was in error? That seems more likely than P==NP.
If P==NP, then any company that wants to pump 10 mil into a fab building will be able to compete with their chip layout strategies.
It's amazing how many math and physics geniuses come out of Russia and other Slavic countries.
Makes me wish I drank vodka as a kid!
Well, it's obviously the vodka!
I can't really comment on the validity of the claims in the article. It's unclear if he has indeed proven P==NP. I do know that this article clearly proves I am only of average or slightly sub average intelligence.
I think God might be sending us a low bandwidth message via P=NP and P=!NP papers. The message can theoretically be extracted by assigning 1 to P=NP and 0 to P=!NP then arranging the bits in the chronological order of the papers (or maybe that should it be 0 to P=NP and 1 P=!NP). The problem is that you can't find "papers" and tech reports which have disappeared down the memory hole and lots of the nutjobs won't have put dates on their offerings. http://www.archive.org/ to the rescue!
The P vs. NP complete problem was introduced in a mandatory class at Virginia Tech (studying for Computer Science). Math is a big part of a CompSci degree now-a-day.
Math has always been a big part of CS. Early CS degrees tended to be a specialized math degree and some CS programs were still under the math department in the 1970s (some in the 80s?) as opposed to CS being its own full fledged department.
There can't be a proof.
A problem is in NP if you can reduce it to 3-SAT (in polynomial time).
Every asymmetrical encryption algorithm in the field relies on the factoring problem, which is NP hard. If P==NP, then suddenly we know the factoring problem is NP easy.
Incorrect.
My personal wild guess is that a large number of the subproblems of an NP question will turn out to be solvable in polynomial time, but a core of "prime problems" will remain which require non-polynomial time.
I have this idea since I know of the queens problem - there are a lot of easy solutions for certain sizes of the board.
Hey don't blame me, IANAB
Is it possible that he just disproved that 3-SAT is in NP-Complete?
So my understanding is that P is the set of problems both verifiable and solvable in polynomial time.
NP is the set of problems verifiable in polynomial time, but we can't currently solve in polynomial time
NP-Complete is a set of problems in NP where one can be reduced to another in polynomial time, so if you could solve one in poly time you could solve all in poly time
3-SAT is NP-Complete.
So assuming this code is correct (which sounds very unlikely), wouldn't it merely prove that NP-Complete is in P? Not to say this wouldn't be a major result, but that's not the same as the more general P==NP.
Am I misunderstanding something?
I stole this Sig
First, the discrete logarithm problem is equivalent to factoring - i.e. a problem of one type can be translated into the other. Second, we can construct a binary circuit to compute products, and iteratively apply 3-SAT to narrow down the inputs until we have a factorization. So if 3-SAT is in P, then so is factorization and discrete logarithm. I'm not aware of the opposite being proven - that if factoring is in P, then P==NP does not necessarily follow.
I saw code like this when I worked on an implementation of Levenberg Marquardt that I had to migrate, on a neural network toolkit, and on an Ant Colony Optimization program I ended up optimizing. It's full of needless interfaces and classes, and it's too objectified to be understandable. Usually, I throw everything away and start from scratch.
By the way, I'll give credit where credit is due: if the algorithm is what it's stated, then let congratulations be given to them. Until then, all I see is a yucky mess.
Never send a comp-sci to do an engineer's work.
I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!
lolwut? Since when has math NOT been a big part of computer science when computer science is a branch of mathematics? You must conflate computer science with programming or software engineering.
Math shmath. It's much more logic than math.
It is Axiomatic Mathematical Logic, a branch of Mathematics. So to say CS is "more logic than math" does not make any sense, unless you are conflating Axiomatic Mathematical Logic with Logic in the broader/philosophical sense.
Unless you count logic as part of math, but I don't.
How does it feel to stand in a does-not-compute vantage point? Seriously, any CS graduate worth its CS salt knows (or should know) that the logic piece in computer science is simply axiomatic mathematical logic and set theory.
Finite State Machines? Logic Grammars? Logic Resource Contention? Logic Composite Systems? Logic Encryption? Logic and the ability to multiply and divide numbers, which is about as "math-centered" as paying your bills.
No.
Yes. Every single example you mentioned involves theory of computation (which utilizes but it is not the same as axiomatic mathematical logic) in addition to discrete mathematics, combinatorics, axiomatic set and category theories, and graph theory. Please entertain me by telling me that the last four are not branches of mathematics.
As for encryption, it is based on number theory and abstract algebra. Fields, rings, eliptic curves, that's all way above the ability of multiplication and division, serious subjects in Mathematics proper. Seriously, where did you get your CS education from?
I am trying to parse the article now. There's very likely a fish in there somewhere.
Note that the Cornell library has hosted at least one other "proof" by a Russian researcher that 3SAT != NP (and that TSP != NP as well).
This paper said you might not need as many dots in step 2, so you get to PROFIT sooner!
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Romanov's algorithm strongly resembles an algorithm from a debunked paper published around 2004.
Sergey Gubin wrote a series of similarly designed proofs around 2004. Instead of Romanov's notion of "concretization," Gubin used the term "depletion." Gubin's paper was debunked by some students at the University of Rochester.
Both reduction algorithms throw out key information about the original truth tables that cause the final solutions to be incorrect.
Constructive and exhaustive proofs that P != NP should never be trusted. I'm not a huge fan of formality in proofs, but sometimes you really need it.
People always talk about the impact P==NP would have on cryptography, but a much more world-changing impact would be on mathematics:
...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems.
http://en.wikipedia.org/wiki/P==NP#Consequences_of_proof
Lots of really smart mathematicians have been trying to find proofs that P==NP for a long time, and they've got lots of good tools to work with. None of them have succeeded. They've also been trying to prove that P!=NP, but that's probably much harder to prove, or at least to validate, since a constructive proof that P=NP has lots of testable examples.
Occasionally people make assertions that they've got a proof that either P==NP, or P!=NP; if they're smart they get them peer-reviewed and find the mistake, but maybe they get to improve our understanding of the general problem or some more specific hard problem, so at least they get a paper out of it. If they're not smart, they just publish it on the InterWebs, and either become net.kooks or have someone gently explain to them how the academic research process works, but the fact that they don't know suggests that they haven't read all the standard research. If they're greedy, they try to patent it, and if it gets past the Patent Examiners they can try selling it to a Patent Troll.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Social Processes and Proofs of Theorems and Programs by DeMillo, Lipton, and Perlis. Let the social process begin.
Why not create your own incomprehensible CS paper?
http://pdos.csail.mit.edu/scigen/
There's no -1 for "I don't get it."
what does P stand for?
Portman.
No no. We know that P is Porter.
I'm pretty sure factoring and discrete log are not known to be equivalent. This would be a huge result in theory of crypto if it could be shown.
Here's your evidence:
Given a public key for an asymetric cryptosystem (say a modulas n for RSA) it is easy to verify (i.e. in NP) that a candidate secret key (say primes p and q in the RSA case) match the public key. Paraphrasing heavily now: If P == NP then anything that is easy to verify if polytime is also easy to solve in polytime. In our case that means if i give you a public key you can now FIND a matching secret key in polytime. I.e. if i give you n which is an RSA public key you can factor it into primes p and q. But if you can find the secret key for any public key algorithm (including RSA) then no such algorithm can be a "secure" cryptosystem.
Heading off some misunderstanding: We do not know how to base security ONLY on P != NP. In fact that is considered one of the largest open problems in modern theory of crypto. While I just argued that P!=NP is a _necessary_ condition for all asymmetric (and most symmetric) crypto to be secure it is not known to be _sufficient_.
We're getting closer with some of the recent advances in Lattice based crypto but were are definitely not their yet. For the theory people out there: A fundamental problem here is that NP tells us something about worst case hardness but for crypto we need average case hardness (i.e. for a random secret key and random coins for the ciphertext). Bridging this gap is highly non-trivial. Recent work in lattices has shown such connections and how to use it for certain problems. However the choice of parameters we use for the resulting cryptosystems are not known to result in NP-hard underlying problems.
What would happen if you tried to express cracking an AES key in 3-SAT form then asked this program to solve it? Will it have to introduce exponentially more variables?
I figure that if anyone claims to have a 3-SAT algorithm, we should ask it to try something infeasible like crack an AES key.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
javascript:document.body.appendChild(document.createElement('div'));
into a link and bookmark it. I have it on my bookmark bar and when ever I need to paste into slashdot I click on the textbox then the button in my bookmark bar labels Fix /.
The Kruger Dunning explains most post on
Get into your car. Drive to the college. Take some courses.
The Kruger Dunning explains most post on
I think the hole in your logic may be that 0.333... == 1/3. I think 0.333... may only be a very close numerical approximation of 1/3, ...
Ditto.
... but 1/3 cannot be expressed absolutely as a number (even assuming infinite 3s).
It can be done, actually. It just cannot be done in base 10! You need to use a base that's a multiple of the prime number 3. ("trinary"?)
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
be a shame if it never finished, or took longer than the age of the universe on a computer the size of a planet before you got an answer.
You want an answer before you need to get your PhD. thesis written, maybe we can fix somethin' for you.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Anyone that thinks they know a lot is a fool.
Sure. Think about 1 - 0.999... it gives you 0.000... = 0. You might worry about a 1 sitting out there in the "infiniteth" decimal place, but remember that you can never get there; the 1 never happens. Since 0.000... = 0 then 1 - 0.999... = 0 and 0.999... = 1. Nothing fancy.
Sure it does, it just takes an infinite number of 0's to get there. The two are indeed infinitely close. Now for the conundrum: 0.999... is an irrational number, not an integer. 1 is an integer. Both belong to R, but only 1 belongs to Z. There may be many applications for which they are functionally equal, but they simply cannot be equivalent.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
My department once had a bunch of physicists writing simulation code, because some of what they were simulating behaved in physics-like ways. I was running the computer, because that was back when you often wanted Computer Nerds to do that for you, though I was really a simulation jock and math nerd.
They were in fact using linear searches through a linked list to manage their event queue in O(n^2) time, and when I made them use a heap to get O(n log n) behaviour, I was disappointed that it only sped up their system by a factor of 5; apparently their code was doing some work besides managing the event list. Also, the system they were modelling basically bounced randomly around a large matrix that didn't fit into our huge 4MB RAM (this was ~1984), and crawling through the linked lists got them some physical locality so it wasn't always paging. A couple of years into the project, memory technology and price had improved enough that we were able to upgrade the VAX to 16MB, and suddenly the program could run in an hour instead of a week, though by that time we'd been able do enough research to tell the end user that the solution we were modelling wasn't really a good one, so being able to run a few hundred more examples a week let us pile on results to help convince them.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
At the very least, then, they are saying that there are interesting subsets of the problem-space that are not truly NP but have been classed as such because the general case was.
This could lead to some very interesting consequences.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Independent of what washes out with the paper / proof...
As someone who has written SAT solvers and solves SAT instances every day... the performance of this implementation is terrible.
I was going to download it -- and then I read this on the github page:
Note that it took about 14 hours for this reference implementation to solve satisfiable 3-SAT instances with variable count = 398 and number of clauses = 1040 (flat50-115 from "Flat" Graph Colouring set).
That 14 hour instance is *ridiculously* easy... for perspective, I tried a few off-the shelf popular SAT solvers and they were all < 0.01 seconds to solve it.
Sure, there are problems that are exponentially hard that you can still often solve for small n, and there are problems that are exponentially hard in the worst case but usually only take polynomial time if you're lucky, and sometimes you can depend on usually being lucky, and there are problems that are exponentially hard if you need the best answer, but have polynomial solutions that will get you within X% of the best answer, which may be good enough.
Cryptography is not any of those problems - you can solve for small n, so the crypto designer just uses a key that's long enough not to be small, and maybe encryption takes twice as long but cracking takes 2^100 times as long. Inexact answers are good enough for the Travelling Salesman Problem, because taking 50% longer to reach all your destinations is still feasible, but guessing one bit wrong in a crypto key usually means that half the output bits are different and you don't know which ones.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The secure channel for a one-time pad is a guy with a briefcase handcuffed to his arm, optionally wearing a tuxedo or a uniform or accompanied by an armed guard. Occasionally there are other options, such as a pressurized conduit between nearby buildings, with the data carried over a fiber-optic system, but that's also depending on physical security for protection.
If you've transmitted your code pad over any physically eavesdroppable medium, it's no longer a one-time pad, it's just a chunk of data encrypted with whatever encryption algorithm the transmission medium used, no matter what the sales guy for the "one-time pad" company told you.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Heh. Who knows what his uncle Nicholas and his cousins Anastasia and Alexei could have done had not the bloody commies killed them in 1918...
To be precise, probably nobody's built one on purpose...
If you're asking whether non-determinism exists in the physical world, that's really a metaphysical question, and you should ask a philosopher or your local quantum mechanic. In the cryptography business, the closest related problem is "If you've stolen a key from your target, can you tell if it's the right one?"
The original Turing machines had infinitely long tapes, which is easy to do if you don't have to build one of them. Since the original work in NP-Completeness, there have been a bunch of further problem classes defined that may constrain the size of the Turing machine, e.g. PSPACE problems with can only be run on a system with space that's bounded by a polynomial function of the size of the problem, so you potentially could build them for some reasonable sets of problems. More years, more PhD theses, more professors needing to publish papers, more problem categories.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
If you're working in a given field, there may be problems that are more like the one you're working on than 3-SAT, so you can reduce to/from them, which will often be much easier and more efficient to prove, even if it's a less efficient way to solve 3-SAT. If your goal is theoretical, that's fine - Reduce FOO to BAR, BAR is known to be NP-Complete, Deliver Thesis.
If your goal is practical, because you want to solve real instances of FOO, tell you it's NP-hard may say you shouldn't try to find the optimal solution but look for near-optimal heuristics, or maybe you should reduce it to BAR, which already has a good near-optimal heuristic or has an optimal solution that's usually but not always fast. Or it may be that knowing that FOO is NP-hard tells you to give up and solve a different problem instead (e.g. in cryptography, where inexact solutions are useless so maybe you should put a keylogger in your enemy's keyboard or drug the courier who's got the one-time pads instead.)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
"including one that runs in time (4/3)^n and succeeds with high probability."
I'll create one that runs in O(1) time and succeeds with very low probability.
Oh ye of little faith. Bear with me as I show you how.
Imagine an infinite series of pairs. Let's start with .9 and .1. This pair total 1. The next pair in the series is .99 and .01. It also totals 1. Following that is .999 and .001, and so forth. As the number of 9's increases, so too does the number of zeros. But there must always a 1 on the end. It is vital for the series to be correct. You can't just assume that it goes away as you approach infinity; it's part of the definition of the series. If you have infinite 9's, than it must be paired with [infinity-1] 0's and a 1, and together will total 1.
If a solitary 1 at the end of infinite 0's is impossible, then so too is an infinite number of 9's. They are opposite sides of the very same coin.
Another way to think about this: we're talking about the set of real numbers. This set is a continuum. In other words, between any two points lie an infinite number of other points. This must mean that some points are infinity close to each other. It's just the nature of the thing. 0.000...0001 is just such a number. It is infinitely close to 1, but not equal to it. There must be such a number, or there could be no continuum. The set of real numbers could not be.
A mathematician would surely say it's much more complicated than that, but you get the idea.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
I know you've gotten a ton of other answers, but I think your fundamental difficulty is in the analogy you're trying to employ.
0.999... is not a equation or sum approaching a limit, it is a single number. The fact that we read left to right does not mean that there is any actual evaluation happening as our eyes drift down that long, long row of 9's. Each 9 is not a subsequent point on a line that is approaching an asymptote. The entirety of (0.99... ) represents, itself, a single point on the line of the reals. That point is infinitely close to 1, and is stationary...it's not "approaching" 1, it's already there and it's sitting right on top of it. It's the same point.
Hopefully this geometric analogy will help. ;-)
Build a man a fire, he's warm for one night. Set him on fire, and he's warm for the rest of his life.
"==" usually means "test whether both sides equal" whereas "=" means things on both sides really do equal.
It irks me that people tend to think == means that things equal; more equal signs does not make the statement more valid, on the contrary, it makes one question the validity in a way..
Assertion to be tested
.999... = 1
.999... = 9.999... .999... = 9.000... ((10-1)*.999) .999 is equal to 9.000... /9 = 1.000... .999 is = 1.000...
Rationale:
because 10 X
9.999... -
so 9 times
so 9.000...
so
so either (1.000... is not equal to 1) or (.999... is equal to 1). So math goes with the second.
You're clearly a communist trying to pollute our Precious Bodily Fluids. (I'm intrigued that that actually spell checks. A "sanity check" would fare much worse. Oh, well.)