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."
Ohhhh my god, someone modded this insightful.
P is polynomial time.
NP is non-deterministic polynomial time.
They're algorithmic complexity classes.
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/
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).