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."
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.
Ohhhh my god, someone modded this insightful.
P is polynomial time.
NP is non-deterministic polynomial time.
They're algorithmic complexity classes.
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
There are fast solutions to the TSP, they're just not fast in pathological cases.
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
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 :)
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.
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