Slashdot Mirror
Claimed Proof That P != NP
morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."
I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.
I was a afraid he might have left out an important step.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.
If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.
Anyone who loves or hates any language, platform, or manufacturer, doesn't know what they're talking about.
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify. So, if the paper is true, then it doesn't really change a whole lot, except that now we know that some day there isn't going to be a trivial solution. I guess its good for cryptography.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.
You can read section one (the introduction) and get a high level walk through of what he's doing. Just be prepared to have a requisite in the following to make it through that:
In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.
My computer science, math and statistics are still fairly sharp but the physics and graph theory are a bit much. Indeed this will take a while to digest. If he hasn't made a mistake in something like bridging together least fixed point logic and functions with Markov-Gibbs properties (correspondence and equivalence).
On the one hand it seems this will take a general expert in the math related sciences to verify but on the other you would think that -- like with the E8 and Lie groups -- this sort of proof would require a rather large unified theory to be able to reduce the N=NP? problem down to a provable situation. I'm no expert and it's been three or four years since I've even been in academia but even the subsections of this paper are noteworthy if they are true. It could be we're looking at something that jumps so far ahead like the famous papers of Turing and Shannon.
My work here is dung.
Of course they're not equal. It is revealed in Futurama episode 2-07.
You can still solve NP problems, just not in polynomial time. There ARE solutions to travelling salesman, just not fast ones...
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
"Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"
From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution
That was a different paper, published in 2005:
http://portal.acm.org/citation.cfm?id=1185240
If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ seems oh so appropriate here. (especially the alt text)
There are fast solutions to the TSP, they're just not fast in pathological cases.
I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.
Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.
Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.
Also, nice typography.
entropy happens
Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify.
I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.
Live today, because you never know what tomorrow brings
At the time of writing, there are two comments on Greg Baker's blog, congratulating Vinay on making it onto Slashdot. Jeez...he's potentially solved one of (if not) the most important open problem in computing, which could land him a million dollars in prize money...but yeah...well done on making it into that most esteemed of online publications, Slashdot.
Are you raving mad?
Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.
There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).
What would be the use of a proof that no human can understand?
entropy happens
It's funny how we don't hear anything from HP for ages, then as soon as there's a sex scandal involving the disgraced CEO, out come all sorts of distractions.
I smell a rat. Okay, I smell 2 rats - Mark Hurd (ex-CEO) and HPs' spin department.
No, there really are solutions (not approximations) for many NP-complete problems that are fast on most inputs. For example, current SAT algorithms are fast on most instances. There are, however, pathological cases on which the algorithms are slow. The fact that a problem is NP-complete just means that, if P!=NP, there is no algorithm that is guaranteed to be polynomial-time for all inputs. It is still quite possible to devise algorithms that are fast for almost all inputs, but slow on a few pathological ones.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
But the margin is too narrow to contain it.
If you can read this, it means that I bothered to log in.
Now that, my friend, is +5, Funny. Nothing here has been fixed in years.
I agree scribd sucks. You can find a link to the PDF from this page which also collects other proofs of P = NP, as well as proofs of P != NP. Pick whichever you prefer :)
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
NP-class problems can be translated into minesweeper puzzles. The problem is determining whether a solution exists in polynomial time. Your example is not solvable. The problem is determining whether a solution can be determined for arbitrarily large puzzles in a polynomial-scale algorithm, or whether the amount of time needed basically grows exponentially. This guy is saying that it grows basically exponentially.
See here for a more complete explanation: http://www.claymath.org/Popular_Lectures/Minesweeper/
The point is that if P did = NP, then there wouldn't be any reason to think further about whether RSA is an NP problem. The constants might be huge, but there would clearly exist a poly-time algorithm for solving it. If P != NP as this result claims, then there may not be one, which is what cryptographers hope.
We'll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
Even if P=NP, polynomial solutions requiring time n^99 consume enough time to be practically infeasible. Thus, even P=NP would not harm cryptography much, if it did not provide very efficient solutions for every NP-hard problem. On the other hand, favorite cryptographic hard problems, such as factoring, are not known to be NP-hard and may well turn out to be solvable in polynomial time, even if P!=NP. Therefore, proof that P!=NP won't have any interesting implications for cryptography unless it contains new ideas that can help in other ways. Neither will proof P=NP unless it includes ideas for fast solutions of interesting problems, such as fast factoring or fast discrete logarithm. Proof of P!=NP may help to solve another interesting problem in cryptography: one-way functions. Right now many results are built on the assumption that such functions exist, but nobody have found a single provable one-way function (easy to compute, infeasible to reverse). A bunch of functions are believed to have this property, but not a single one has been proved difficult to reverse. I would be interested to see if this proof will produce such an animal - a provably one-way function.
Sorry, I wasn't clear. I meant what's the next big problem in computer science.
Assuming this proof holds up, the next set of questions are how much the complexity hierarchy breaks down. There are a host of complexity classes between P and NP. Other important classes include PP and BPP http://en.wikipedia.org/wiki/BPP, http://en.wikipedia.org/wiki/PP_(complexity). BPP is a subset of NP and is tentatively believed to be equal to P. Another important class is BQP http://en.wikipedia.org/wiki/BQP which is the class of problems which can be solved quickly by a quantum computer. If this proof goes through it may generalize to showing that some of these other classes are distinct (proving that BQP is not equal to P would be almost as big a deal as proving that P !=NP).
You don't need to simulate the Turing machine. You just need to encode it as a boolean formula. That's part of what Cook's theorem shows; it shows how to encode a non-deterministic Turing machine as a boolean formula with at most a polynomial increase in size. Now that the problem is in a NP-complete form just follow the reductions until you get to the NP-complete algorithm that has a P algorithm. In this way you can solve any NP problem in P time as long as you solve one NP-complete algorithm in P time.
Chris Mesterharm
I think you are misunderstanding what the P=NP question means... and I don't blame you. The question itself is very "meta", but it is not self-referencing as you believe.
P is a set of questions (YES/NO questions) that can be answered easily. NP is another set of questions, that may or may not be easy to answer, but when you see the answer (YES/NO) and a proof for the answer, you can easily check if the proof is correct. But the question "P=NP?" doesn't belong to either of the sets. If P=NP, then all problems that are easily "verifiable" are also easily "solvable", and if P!=NP, then there are problems easily verifiable but hard to solve. But, as the question "P=NP?" doesn't belong to P or NP, there is no paradox.
That's an over simplification, of course. For instance, "easy" in the previous paragraph actually means "solvable in polynomial time by a deterministic turing machine", and "not easy" would be "solvable in polynomial time by a non-deterministic turing machine", and there is the widespread confusion about "NP" meaning "Non-P" instead of "P in a Non-deterministic machine". The wikipedia article is really good, but unfortunately, much too formal to understand without previous knowledge. I hope I helped a bit.
IMO, The P vs NP is fundamentally more tricky than other famous theorems/conjectures (like FLT), because on some level it is a statement about mathematics itself. The assumption that P != NP on some level implies that the finding mathematical proofs is difficult. This means that if P!=NP it may be even more difficult to prove that P!=NP. It has been shown that assuming one-way functions exist (this would imply P!=NP easily enough) that a certain type of proof called "natural proofs" can never be used to separate P from NP.
On the flip side, showing P = NP could be easier, but most people believe this is false, since it would mean that there is essentially one "master algorithm" that can solve any problem in NP efficiently.
The current state of computational complexity theory is that we are no where close to resolving P!=NP, that is unless this proof actually checks out. Honestly, we can't even settle "easier" questions like P vs PSPACE. The implications of a correct proof would be absolutely mind blowing.
That's one hell of a spin department.
Some university really should hire them, because if they can prove P!=NP just to cover up a sex scandal, imagine what they could do if they didn't waste time writing press releases.
Oh man, if you think the politics and backbiting are bad in typical academia, wait until you see an entire computer science department arguing over who gets to have illicit sex in order to set off the proof-generating team.
"This algorithm runs in constant time. Come on, 2,147,483,648 is a constant..."
Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:
It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.
Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.
The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.
I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).