Claimed Proof That P != NP 457
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."
Re:What would the impacts of this be for cryptogra (Score:4, Informative)
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.
Re:Well, duh (Score:5, Informative)
Ohhhh my god, someone modded this insightful.
P is polynomial time.
NP is non-deterministic polynomial time.
They're algorithmic complexity classes.
View from the future (Score:5, Informative)
Re:Makes my job easier... (Score:5, Informative)
Re:From the wikipedia discussion page (Score:5, Informative)
"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 [wikipedia.org]
That was a different paper, published in 2005:
http://portal.acm.org/citation.cfm?id=1185240 [acm.org]
Re:What would the impacts of this be for cryptogra (Score:1, Informative)
My analysis said DH would hold even if P=NP.
I had a lower bound on the order of the polynomial for breaking DH and it was something like 256. There's really not much practical difference between n256n for n = 4096. Both are practically intractable.
Re:What would the impacts of this be for cryptogra (Score:3, Informative)
I meant asymmetric, which is what RSA is. Symmetric keys are usually exchanged relying on the discrete logarithm problem (RSA problem [wikimedia.org]), not the integer factorization problem.
Re:Makes my job easier... (Score:5, Informative)
There are fast solutions to the TSP, they're just not fast in pathological cases.
Re:What would the impacts of this be for cryptogra (Score:2, Informative)
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.
The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.
Re:What would the impacts of this be for cryptogra (Score:2, Informative)
Large integer factorization has not been shown to exist in NP-Complete (it is doubtful it does), it is know to exist in both NP and co-NP, it could exist in P (but it is doubtful) we just don't know. RSA public key crypto depends on the difficulty of factoring very large numbers. Currently there is no known efficient mechanism for determining the factors of a very large number. If P != NP we don't get a whole lot more than we have at the moment because we don't know exactly what complexity class integer factorization lives in. If P == NP then we have a serious problem because that requires there to be an efficient integer factorization algorithm. It is interesting that if P != NP we could very well end up in a situation where there are problems that have no efficient solution (not in P) but are not in the class NP-Complete (the "hardest" of the problems in NP). Integer factorization could very likely fall within this area.
Re:Makes my job easier... (Score:5, Informative)
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.
Re:Is there a link to the actual preprint / paper? (Score:5, Informative)
Try this: (Score:3, Informative)
http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof [wikipedia.org]
Consequences of proof
One of the reasons the problem attracts so much attention is the consequences of the answer. A proof that P = NP could have stunning practical consequences, if the proof leads to efficient methods for solving some of the important problems in NP. It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice. The consequences, both positive and negative, arise since various NP-complete problems are fundamental in many fields.
Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced.
On the other hand, there are enormous positive consequences that would follow from rendering tractable many currently mathematically intractable problems. For instance, many problems in operations research are NP-complete, such as some types of integer programming, and the travelling salesman problem, to name two of the most famous examples. Efficient solutions to these problems would have enormous implications for logistics. Many other important problems, such as some problems in protein structure prediction are also NP-complete;[15] if these problems were efficiently solvable it could spur considerable advances in biology.
But such changes may pale in significance compared to the revolution an efficient method for solving NP-complete problems would cause in mathematics itself. According to Stephen Cook,[4] ...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.
Research mathematicians spend their careers trying to prove theorems, and some proofs have taken decades or even centuries to find after problems have been stated - for instance, Fermat's Last Theorem took over three centuries to prove. A method that is guaranteed to find proofs to theorems, should one exist of a "reasonable" size, would essentially end this struggle.
A proof that showed that P NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P NP, much of this focusing of research has already taken place.[16]
Re:Implications (Score:2, Informative)
Re:Rats! (Score:3, Informative)
Re:Proof by example? (Score:5, Informative)
See here for a more complete explanation: http://www.claymath.org/Popular_Lectures/Minesweeper/ [claymath.org]
Re:What would the impacts of this be for cryptogra (Score:3, Informative)
If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.
Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so it's not actually possible to provide a truly non-constructive proof that P=NP.
Re:What would the impacts of this be for cryptogra (Score:5, Informative)
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.
Re:Two questions (Score:5, Informative)
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 [wikipedia.org], http://en.wikipedia.org/wiki/PP_(complexity) [wikipedia.org]. 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 [wikipedia.org] 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).
Re:XKCD was right (Score:3, Informative)
Am I the only one who had to Google 0x5f3759df? http://en.wikipedia.org/wiki/Fast_inverse_square_root [wikipedia.org]
Re:Wouldn't P=NP be a paradox anyway? (Score:3, Informative)
Re:Not in arXiv? (Score:3, Informative)
Circulating it among colleagues for review is exactly what he was doing. See the author's personal web page: http://www.hpl.hp.com/personal/Vinay_Deolalikar/
He says there that "The preliminary version made it to the web without my knowledge. Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned."
Re:What would the impacts of this be for cryptogra (Score:5, Informative)
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.
Re:I have found an excellent proof of this... (Score:1, Informative)
Fermat, not Euler.
Look up "Fermat's Last Theorem".
Determinism WRT Turing Machines: a primer (Score:2, Informative)
A Turing machine has a state (from a finite list of possible states), a table of operations to be performed based on input and state, and an input - nominally considered an infinite tape preloaded with an input string (a series of symbols from a finite set) with the remainder blank. Input symbols can be data or action symbols (data or program). The machine proceeds from its initial state processing operations from its table based upon its state and input until it finds a state that's "Accepting", and halts. A problem is considered soluble by a TM if any potential input, operated upon by the machine in exact accordance with the table can move the state to an "Accepting" state. For the purposes of Turing Machines, operations take 0 time and the machine is immortal. From the beginning these are not presumed to be mechanical or electronic machines, but rather a theoretical human who executes the instructions without any bias or thought to the outcome. Turing Machines are a thought experiment, not physical machines. They are hypothetical. They are, however, widely used in information theory as well as other fields including physics.
/Non Sequitur: Alan Turing [wikipedia.org] was a Brit who confessed to being queer, was chemically castrated and deprived of his security clearance as punishment, and is supposed to have killed himself at 42 with an apple laced with arsenic, a-la Snow White. We'll never know what more he might have given us. Homophobia cost us one of the greatest minds of the 20th century. His work is now considered fundamental to our understanding not only of what computers can do, but of the nature of the universe.
A Deterministic Turing Machine (DTM) is one that has at most one action for a specified state, action symbol and input. A Non-Deterministic Turing Machine [wikipedia.org] (NDTM) may have more than one.
To say that P!=NP is to say that the Non-Deterministic Turing Machine can find an Accepting state that the Deterministic Turing Machine can not.
In the case of a NDTM with more than one potential action to be performed for a specific state and action the Turing Machine (TM) can be considered to clone itself, which each clone performing one of the indicated actions - in essence creating a tree of potential Turing Machines. Alternately the Turing Machine can be assumed to select the action that results in the Accepting state if there is any. AFAICT the potential for input strings to come to the Accepting state on divergent paths is moot as any Accepting state will do, and in the case where divergent "leaf" TMs Accept the input or enter infinite loops, an Accepting TM wins. This isn't an input validation routine: the determination that the input is invalid is an Accepting state.
I haven't read TFA, but I would imagine that the proof for P=NP would involve finding one problem where the non-deterministic machine found a solution that a deterministic machine couldn't. Presumably this involves solutions hidden by infinite loops.
Really, the idea is silly though. It's Garbage In, Garbage Out. If your Turing Machine needs non-determinism it's because it's potentially operating on unknown data or processes and so its state/action table is inadequately defined. This is an abuse of the machine. It results in solutions for problems that are NP, but the only rational course is then to dissect the tape, find the successful branches of potential choices, find the unknowns and rebuild the machine's state/action table to include these potentials. We call this process "the scientific method". To fail at this, the unknown thing that caused the effect must be unknowable. In fact, any such Turing Machine can be redefined to permute across potential state/action/input triplets, or to include the reconciliation of the result to the process, and the question devolves into the halting problem, so the problem becomes the impossibility of iteration against possible out
Re:Well, duh (Score:2, Informative)
But ACs can't bank karma. I guess someone had mod points to burn.
As a /. reader, I appreciate moderation to increase visibility for worthwhile comments. Your karma score doesn't mean dick. I doubt the moderators care about your karma score either. BTW, does /. have a neutral sort yet (a sort that only reflect moderation changes not the starting value? Add it, I may just log in agan after 10 years. Hell, I just may pay too.
Simple Description (Score:2, Informative)
Re:Not in arXiv? (Score:3, Informative)
``Also, nice typography.''
At the risk of pointing out the obvious, that's what you get when you use LaTeX [latex-project.org]. You focus on the content, and LaTeX takes care of the typesetting, incorporating years (perhaps hundreds of them) of research on how to make text aesthetically pleasing, easy to read, and suitable for binding, so that you don't have to do that research yourself. Plus, LaTeX is the format that many journals prefer submissions to be in.
Re:What would the impacts of this be for cryptogra (Score:3, Informative)
I'm being thick here I guess, but why do we know the required simulation of Turing machines to be in NP=P (given assumption), and not EXPTIME or at least PSPACE?
The algorithm is: on iteration N, simulate one (more) step on Turing machines 1 through N. Stop when a machine outputs an answer with a formal proof that answer is correct.
If P = NP, then the M'th Turing Machine does this in P(n) steps. It takes P(n)+M iterations before that happens. Each iteration takes M+i steps, so the run time is O(P(n)^2), which is polynomial! (note that M is an "exponentially large" constant, so this approach wouldn't result in a truly usable algorithm.)
Re:P=NP & P!=NP (Score:3, Informative)
Re:Well, duh (Score:3, Informative)
Not sure if I'm misunderstanding what you mean, but set your options to add +1 to AC posts, remove karma bonus and remove the insightful bonus. All posts start at 1 and all mods are either +1 or -1.