There’s a new paper circulating that claims to prove that P ≠ NP. The paper has not been refereed, and I haven’t seen any independent verifications or refutations. Despite the fact that the paper is by a respected researcher—HP Lab’s Vinay Deolalikar—and not a crank, my bet is that the proof is flawed.
EDITED TO ADD (8/16): Proof seems to be seriously flawed.
EDITED TO ADD (9/11): Proof is wrong.
fraac • August 9, 2010 3:11 PM
Do you think it’s unprovable?
AlanS • August 9, 2010 3:11 PM
OT but presumably something a normal person might be able to solve: “We’d like to go on record and announce that the 2010 DBIR Cover Challenge is officially on and that the $500 is still up for grabs (along with 2nd and 3rd place prizes). Beyond that, our lips are sealed. Happy hunting.”
http://securityblog.verizonbusiness.com/2010/08/09/who-wants-500/
AMADANON • August 9, 2010 3:14 PM
If you find has been “proved” many times with flaws, and you start betting against new proofs, you will only be wrong once, at most.
Afonso Araujo Neto • August 9, 2010 3:24 PM
I can’t help but remember the Fermat’s Last Theorem proof by Andrew Wiles, which turned out to be flawed in it’s first version. Using the peer reviews he got, however, he was able to correct it.
Actually, there already is some speculation about the kind of flaw the the proof may contain. An initial discussion can be found in the comments on this blog post http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
Flawed or not, now that the ideas are in the wild, they can be improved by a large number of researchers. It seems to be an important input (contrary to the majority of proofs out there) because it ingeniously builds upon recent discoveries in the field. It may well be the first real step in the solution of the problem..
meepmeep • August 9, 2010 3:26 PM
Here’s the paper: http://www.scribd.com/doc/35539144/pnp12pt
Pierre de Fermat • August 9, 2010 3:27 PM
I, too, have discovered a truly marvelous proof, but unfortunately the comment section of this blog is too narrow to contain it.
Phillip • August 9, 2010 3:29 PM
OK, I’m a math idiot. Can someone explain to me the bearing this has on encryption or security?
Does it make public/private key pairs easier to factor?
Afonso Araujo Neto • August 9, 2010 3:34 PM
@Philip No… But it would prove that it is POSSIBLE that there MAY be NO way to easily factor. 🙂
Ciaran McNulty • August 9, 2010 3:36 PM
Philip,
Most asymmetric keys rely on NP problems being insolvable in P time, it’s just never been proven that this set of problems don’t have P time solutions.
So basically if the proof holds it removes the sneaking suspicion that some bright sparck can find a way of factoring primes quickly and breaking all our odds.
Nothing is perfect. It’s worth $1 million. Nice prize.
Short version, as I understand it: public key cryptography assumes that, for all practical purposes, P≠NP. Proof that P=NP would lead to the field’s inevitable demise, since it would eventually make computing someone’s private key, given their public one, doable in a reasonable amount of time. Likewise, proof that P≠NP, such as what this paper claims to have, would prove the fundamental assumptions of public key cryptography are sound, and the field is safe.
Bruce Schneier • August 9, 2010 3:45 PM
“Any reason you think this one is flawed ? and do you mean typo-flawed, or major-flawed?”
Major flawed. And I’m saying this with no knowledge of the paper. I just don’t believe I’m going to see that proven in my lifetime.
Bruce Schneier • August 9, 2010 3:46 PM
“Do you think it’s unprovable?”
No, I just think it very unlikely to be proven.
But — as someone pointed out above — lots of us believed the same thing about Fermat’s Last Theorem.
Bruce Schneier • August 9, 2010 3:48 PM
“Flawed or not, now that the ideas are in the wild, they can be improved by a large number of researchers.”
Even if the proof turns out to be wrong, I think it will increase the body of knowledge on the topic.
Afonso Araujo Neto • August 9, 2010 3:50 PM
@Ciaran McNulty
Actually, that is not true. The proof is based on the idea that SAT (hence NP-complete problems) is hard, and therefore NP != P. However, factoring was never proved to be NP-complete. The proof would only imply the impossibility of easy factoring IF factoring is NP-Complete, which no one knows.
Bruce Schneier • August 9, 2010 3:50 PM
But, at least the proof is in the correct direction. A proof that P=NP would be a problem.
Afonso Araujo Neto • August 9, 2010 4:04 PM
“But, at least the proof is in the correct direction. A proof that P=NP would be a problem.”
Probably not instantaneously, but I’m sure cryptographers would start walking with a “cloud of impending doom” over their heads. 🙂
Clive Robinson • August 9, 2010 4:09 PM
“Despite the fact that verifications or refutations. Despite the fact that the paper is by a respected researcher”
Ouch…
If you think back you will find a lot of major events in mathmatics and physics are by those little more than research grads.
The pedestrian advancment generaly goes to “respected researchers”.
Often this is because of hurd thinking, in that once you are established in a community and have a name you tend to conform to the consensus of the communit lest you become an outcast or potential figure of ridicule.
Joe Buck • August 9, 2010 4:15 PM
Suppose P=NP, and there’s a SAT algorithm that is O(n^100000). Would that state of affairs really change anything?
Tallulah Bankhead • August 9, 2010 4:25 PM
At a dinner Tallulah was being bored by an elderly scientist who expounded on the subject of ants. “They are wonderful little creatures,” he declared. “They have their own police force and their own army -”
In her usual dry tone, Tallulah interrupted, “No navy, I suppose?”
-Irving Hoffman, King Features
David Thornley • August 9, 2010 4:33 PM
@Ciaran McNulty: It’s not just public-key cryptography that would be affected by P=NP.
Deciphering a given ciphertext with a known key is an efficient operation, definitely in P. Therefore, deciphering a given ciphertext, with initially unknown key, to get plaintext with certain parameters, is in NP. Therefore, decryption of any reasonable cipher is in NP, given that we know or can surmise something of the plaintext. Therefore, if P=NP, we can decrypt any message, as long as we have some idea of the plaintext (such as that it’s in English, say), in polynomial time.
(This doesn’t apply to a one-time pad. Getting reasonable-looking plaintext is easy with one, it’s just that we have no way to know which plaintext is correct.)
So, if P=NP, and we can solve any problem in NP in reasonable time, there goes cryptography.
Of course, polynomial time doesn’t necessarily mean reasonable. A polynomial-time algorithm is better than an exponential one for sufficiently large problems, but “sufficiently large” may already require uncounted universes full of computers to solve.
gilberto • August 9, 2010 4:43 PM
Over the years there have been dozens of papers claiming either result, usually under some restricting conditions. Only time, and the referees, will tell. My gut feeling is that P not=NP. Proving either result would probably not have an inmmediate effect on PRACTICAL cryptographic methods. But then again, only time will tell.Many companies, including IBM, tend to get overly creative in publicizing results obtained byt their researchers.
The Navy figured it out. It just hasn’t been leaked.
I can hear all mathematicians and computer scientists at NSA headquarter laugh out loud -> P!=NP
X-D
Everybody knows that they have to handle quantal computers, secured and reengineered by the Roswell incident in 1947. And because of this alien technology, they where able to brute force the AES 256 wikileaks insurance encrypted file in O(1).
NP my ass! 😀
Michael Lynn • August 9, 2010 6:21 PM
@Phillip
This is the (very) short and thus inevitably over simplified answer to your question, but I think it will suffice.
Ok, so to start with P in this case means problems that can be solved in polynomial time. For our purposes we’ll just say that anything solvable in polynomial time is tractable (i.e. we can compute solutions in reasonably efficient time frames). NP means non-deterministic polynomial time problems. So as to avoid lots of the the little details, this basically (although not precisely) means any problem that can only be solved efficiently with a non-deterministic computer (one that can have an infinite number of parallel processes if you will). Put even more plainly (and yes a little more technically wrong but good enough for these purposes), P problems are easy to solve, NP problems are hard to solve.
Why is this important to security and/or cryptography. Well almost all cryptography that I know of is based on problems that are too hard to solve without the key (or so we hope). For example we assume that factoring is a hard problem (i.e. that there is no polynomial time solution for it). Now I’m not aware of any proof (because I’m pretty sure it doesn’t exist) that factoring truly is an NP problem; although most people tend to think that it is. Until quite recently we thought that strict primality testing was NP until a group of undergrads found a polynomial time solution for it, for example.
So if they say P != NP they are saying that the set of all problems that can be solved in polynomial time is not exactly the set of all problems that can be solved in non-deterministic polynomial time. Which basically means, there exist some problems that can-not be solved in polynomial time on a turing machine (unless it is a magical non-deterministic turing machine, but don’t hold your breath waiting for one of those).
The converse would basically kill modern cryptography (with some few exceptions like the one time pad if we can call that modern). If P == NP that would mean that any problem that any NP problem always has a solution in polynomial time on a normal turing machine as well (i.e. it is always solvable efficiently in a tractable way). Put more to the point, it would mean that there should be a shortcut to breaking all our modern ciphers. Of course when I say it would kill it I basically mean it would kill it in the academic sense that we would then know that there is always a solution, it would probably not supply you with the solution outright. So even if they had proven P == NP (something almost no-one expects to be true btw) I doubt it would cause any immediate problems for the field. Then again, sometimes just knowing a thing is possible is all it takes to help someone find the solution.
**
To the mathematically inclined haters before you start: yes I know this is oversimplifying it, and in places technically wrong, but its done so in those places to make it put in plain language to get the point across. Or put another way, shut up.
**
–Michael Lynn
Michael Lynn • August 9, 2010 6:31 PM
@W
“Everybody knows that they have to handle quantal computers, secured and reengineered by the Roswell incident in 1947. And because of this alien technology, they where able to brute force the AES 256 wikileaks insurance encrypted file in O(1).”
Why did it take them O(1)? I mean, for all the money we’re paying them and all the alien tech they are bound to have can’t they do it in O(-1) or something, like they get the answer before they ask the question? 😉
–Michael Lynn
Betta Sharma • August 9, 2010 8:04 PM
“So basically if the proof holds it removes the sneaking suspicion that some bright sparck can find a way of factoring primes quickly and breaking all our odds.
Posted by: Ciaran McNulty at August 9, 2010 3:36 PM”
No; Primes can’t be factored, bright sparks or no!
Also, FWIW, Primes has been shown to be in P recently. http://en.wikipedia.org/wiki/AKS_primality_test
Tom T. • August 9, 2010 8:58 PM
@ Betta Sharma: “”So basically if the proof holds it removes the sneaking suspicion that some bright sparck can find a way of factoring primes quickly and breaking all our odds.
Posted by: Ciaran McNulty at August 9, 2010 3:36 PM”
No; Primes can’t be factored, bright sparks or no!
Would you not give the other poster the benefit of assuming that they meant “factoring the product of two (very large) primes”?
Pseudonym • August 9, 2010 10:28 PM
Something that I find endlessly fascinating is that all known public key and digital signature algorithms (both toy and practical) rely on at least one problem that is in NP, but isn’t (or isn’t known to be) NP-complete, such as prime factoring, discrete log, graph isomorphism etc.
Nick P • August 10, 2010 1:29 AM
@ Pseudonym
Yeah, I’ve always felt public key crypto just didn’t have enough assurance. I think Universities getting crypto funding should be spending more effort developing new public crypto methods, like the more recent lattice-based methods that show immunity to quantum attacks. It seems like the public key crypto area is based on a small number of failure points as far as the math goes. If someone gets lucky here, all of this fails. If someone gets lucky there, all of that fails. We have plenty of options for symmetric and hash functions. We need to fund the creation of more asymmetric crypto schemes that work.
Secure • August 10, 2010 1:29 AM
Don’t take the following too seriously, it just came to my mind when I’ve first read about this, but I’m not too deep into the mathematics and the theory. 😉
There can’t be a final proof for P!=NP, because the proof itself is in NP. You have to effectively prove that all possible and thinkable solutions are in NP and none is in P. This makes the problem somehwat self-referential, thus according to Gödel’s incompleteness theorem, there can’t be a consistent proof.
csrster • August 10, 2010 2:05 AM
Not $1M but $1.2M – Scott Aaronson has said he will contribute an extra $200000 if this proof is correct.
Clive Robinson • August 10, 2010 2:22 AM
@ Secure,
“There can’t be a final proof for P!=NP, because the proof itself is in NP”
Ok I get the reasoning but how do you prove it 😉
!Proof = NoPrize,
flatline • August 10, 2010 2:34 AM
Integer factorisation is certainly in NP but it is unknown whether it is NP-complete. Hence P != NP doesn’t say anything about the efficiency of integer factorisation (RSA) until someone can prove it’s NP-hard and thus in NP-complete. The consensus is that it is in fact not NP-hard.
Also, P = NP is problematic only if one is wearing myopic crypto glasses.
Winter • August 10, 2010 3:01 AM
What if P=NP, that is, every problem whose solution can be checked easily can be solved easily.
However, finding the solutions is beyond P and NP. That is, every “NP complete” problem has a solution in P, but proving any solution is just as hard as finding it.
Maths Idiot • August 10, 2010 6:02 AM
Surely if N=1 then P = NP ?
Jason Trost • August 10, 2010 6:09 AM
We created a prediction market for who will be awarded the next Clay Prize. http://smarkets.com/current-affairs/clay-prize/next-winner
Let me know if there are any other markets that you guys might want to see.
Jason
Founder of Smarkets
Foo • August 10, 2010 6:15 AM
NP in this context doesn’t mean N multiplied by P.
P is polynomial. NP is… not polynomial (though it might have another name).
kevinm • August 10, 2010 6:27 AM
OT @AlanS it may be stego http://www.eriugena.org/blog/?p=61
dreamfish • August 10, 2010 7:03 AM
I suppose one saving grace is that we’re unlikely to see the media trumpet this as a conclusive proof, thus again demonstrating their ignorance of the peer-review process. Unlike something like Fermat’s Last Theorem, P=NP isn’t easily understood by the layman, especially journalists.
Liam • August 10, 2010 7:26 AM
Just a heads-up:
There seems to be a lot of confusion over terminology in the comments here. A quick summary:
P, NP and NP-hard only make sense in terms of decision problems, so recall that all problems discussed in that context must have a possible yes/no formulation.
P is the full set of decision problems whose worst case can be decided in polynomial time (O(n^k)), where k is some constant and n is the length of the input in bits.
NP is the full set of decision problems that can be VERIFIED in polynomial time, that is, given an input, an a-priori answer and a “proof” which has a bit length that is polynomial in the size of the input, can be VERIFIED in polynomial time. (I.E, the yes/no answer can be shown to be correct in polynomial time, given this proof). It’s trivial to show that P is a subset of NP. (
NP-Hard problems are a set of problems with the following characteristic: If they have a polynomial-time solution then P=NP.
This proof, if it’s correct, shows that NP-hard problems don’t have a polynomial-time solution.
It’s worth noting, as pointed out above, that this result wouldn’t prove that factoring large numbers, the discrete logarithm problem or the graph isomorphism problem are intractable, as these problems haven’t been proven to be NP-hard. Proving something is in NP doesn’t put any lower bound on the complexity, as P is a subset of NP.
Mark Wooding • August 10, 2010 9:20 AM
@Liam: Minor correction: it’s only yes' answers which have a polynomial-time verifiable proof. Ifno’ answers have polynomial-time verifiable proofs, then the problem is in co-NP. It’s (still) unknown whether NP = co-NP. (If P = NP then they’re the same; otherwise we still have work to do.)
Impact on cryptography: none, really. The interesting questions for cryptography is whether one-way functions and (even more interestingly) trapdoor one-way functions exist.
If P = NP then neither exists, and computationally-secure cryptography[1] as a field of study vanishes immediately. We’re left with one-time pads, Carter–Wegman authentication, and some multiparty computation stuff.
But even if P /= NP, it’s still the case that one-way functions might not exist. And we’re still left without computationally-secure cryptography. Finally, one-way functions might exist, but trapdoor one-way functions might not — in which case we end up with symmetric cryptography and (very cumbersome) digital signatures but not key agreement or public-key encryption.
[1] In the complexity-theoretic sense. There might still be some milage in doing computationally secure cryptography with only a polynomial adversarial disadvantage, but even that’s risky without a lower bound on the polynomial degrees we’re dealing with. And, of course, the constant factors involved are important for any specific, concrete case.
David Thornley • August 10, 2010 9:22 AM
@Liam: To nitpick a bit, you’re using “NP-hard” where you should be using “NP-complete”. An NP-complete problem is a decision problem (example: given a Travelling Salesman Problem, is there a possible route with cost less than N?), and an NP-hard problem is another problem that is equivalent in difficult to an NP-complete problem (what’s the shortest route in the TSP?).
@Foo: NP means Nondeterministically Polynomial, which means solvable in polynomial time by an infinitely parallel computer (i.e., a computer that can be in arbitrarily many states at once, hence nondeterministic). A Non-Polynomial problem would be one that cannot be solved in polynomial time.
@Secure: We can prove things about NP-complete problems without exponentially increasing proofs, so I don’t understand where you’re coming from. It is of course possible that neither P=NP nor P!=NP can be proved consistently, and that’s true for any proposition that we’ve neither proved nor disproved, but there’s no good reason to think so. BTW, NP-complete problems are solvable by brute force, so even if the proof were NP-complete (and I have no idea what that could possibly mean) this wouldn’t apply.
Liam • August 10, 2010 11:07 AM
@Mark – Whoops, your nitpick is correct. My bad. It provides a good example for the following:
@David –
To Nitpick the Nitpick: NP-Complete is a problem that is both in NP-and is NP-Hard: (There are NP-hard problems not yet known to be in NP, such as the complement of the Hamiltonian Cycle problem, which is in co-NP).
Liam • August 10, 2010 11:10 AM
Addendum to above: So yes, NP-Hard is restricted to decision problems. We refer to TSP as NP-Hard in its decision fomulation: “Is there a path with a weight of at most x?”
moo • August 10, 2010 11:22 AM
Lots of people have claimed to have proved that P != NP, and lots have also claimed to have proved that P = NP. All of the claimed proofs so far have been found to be incorrect after public scrutiny.
This page collects a list of many attempts to settle the question one way or the other:
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
It also has a direct PDF download link for Vinay Deolalikar’s latest effort.
I am not qualified to judge the proof and may not even be able to make sense out of it. My gut feeling is that it will contain flaws. Its pretty hard to write a 66-page mathematical proof without making any mistakes. It seems likely that he will have made at least one very subtle mistake somewhere–the kind of mistake that is so subtle that it is only going to be discovered by the scrutiny of hundreds of the world’s best mathematicians. But that’s the whole point of releasing it publically for peer review. Even if it turns out to have flaw(s), this attempt is very probably going to advance the state of the art in this branch of mathematics, and (like with Fermat’s Last Theorem) its possible that any flaws the proof might contain are able to be repaired in a way that will still lead to a solid and generally accepted proof. If so, it will be a very impressive accomplishment and a useful theoretical result.
moo • August 10, 2010 11:27 AM
@Clive:
“Often this is because of hurd thinking…”
Was that just a typo, or was it a freudian slip? This paper comes from an HP researcher, and HP’s CEO Mark Hurd was just ousted, apparently because of some impropriety with the use of company funds to pay for his mistress or something? But anyway the story has been in the media for a few days from various angles and the “hurd thinking” seems to be all too common…
Steve Halter • August 10, 2010 12:00 PM
Here’s a link to a wiki gathering conversations on the paper:
http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper
kangaroo • August 10, 2010 1:15 PM
So everybody is excited that cryptography is safe.
But, if true, this means that many other problems that are NP, but we wish to attack them tractably, are hopeless as well.
If true, this is not unalloyed good news — in fact, it means that many problems are hopeless. Cryptography isn’t the greatest intellectual and political problem we have — this is like being excited about Godel. Sure, there’s some good that comes out of it — but we also have to face a proven intractability of the universe.
That kinda sucks.
Jeremy • August 10, 2010 1:44 PM
@David Thornley:
“Deciphering a given ciphertext with a known key is an efficient operation, definitely in P. Therefore, deciphering a given ciphertext, with initially unknown key, to get plaintext with certain parameters, is in NP. Therefore, decryption of any reasonable cipher is in NP, given that we know or can surmise something of the plaintext. Therefore, if P=NP, we can decrypt any message, as long as we have some idea of the plaintext (such as that it’s in English, say), in polynomial time.”
P and NP are defined for decision problems. If P=NP, it’s clear that we can (efficiently) prove that a valid decryption exists for a given ciphertext, but I’m not clear how you’ve reached the conclusion that we can also figure out what that plaintext actually is.
Care to elaborate?
Liam • August 10, 2010 2:18 PM
@David, Jeremy:
David’s formulation of the question is in terms of a quasi-known-plaintext attack. I think the issue isn’t retrieving the plaintext, it’s retrieving the key after the problem has been decided. You ask the black box: “Does a key exist that turns this ciphertext into this plaintext using this cipher?”. It answers, in polynomial time: “Yes!”. The flaw is assuming that the machine will need to produce the key to determine the question.
Jeremy • August 10, 2010 3:18 PM
I believe he was only assuming that we knew very general properties of the plaintext (“such as that it’s in English, say”), not a known plaintext.
However, upon further reflection, I think I see a way to extract the key: you guess it one bit at a time.
If P=NP, then you can ask “Is there any 128-bit AES key that decrypts this to an English-looking plaintext?”, but you can also ask “Is there any 128-bit AES key whose first bit is zero that decrypts this to an English-looking plaintext?” Once you’ve confirmed that the first bit is (or is not) a zero, you guess the second bit, and so on.
That multiplies the time required by the number of bits in the key, but that’s still polynomial.
DCFusor • August 10, 2010 5:06 PM
I’ve not been paying enough attention I suppose.
Is it still true that a P solution to any NP problem would mean there is a solution to all NP problems? As kangaroo mentioned, there are a few out there that would love to be solved in other than the brute force “proof” that “4 colors suffice”.
And for those that don’t understand — proving that a P solution exists doesn’t give you that solution, just the knowledge that one is possible. However, many problems map fairly closely onto one another and once one is solved, you do get a hint to the others.
Ray • August 10, 2010 6:32 PM
@moo
“Was that just a typo, or was it a freudian slip?”
It was Clive, so my money is on “typo”. 😉
Jeremy • August 10, 2010 6:50 PM
@DCFusor: “Is it still true that a P solution to any NP problem would mean there is a solution to all NP problems?”
Not quite. A P solution to any NP-complete problem would mean there is a solution to all NP problems. But not every NP problem is NP-complete (unless P = NP).
P is actually a subset of NP, so every problem with a P solution is an NP problem. But there are also some NP problems that (we suspect) aren’t in P.
There are also problems harder than NP. Graph coloring is NP-complete, but I’m not sure whether the proof that all planar graphs are four-colorable is itself NP or not.
Mark Wooding • August 10, 2010 7:01 PM
@DCFusor: `Is it still true that a P solution to any NP problem would mean there is a solution to all NP problems?
All of P is certainly contained in NP; so, no, just because we can find a polynomial-time algorithm for some NP problem doesn’t help with any others. But there are some problems for which this would be helpful. They’re called NP-complete. An NP-complete problem has the property that you can take an instance of /any/ other problem in NP, and convert it into an instance of the NP-complete problem, in polynomial time, so that the answer to the NP-complete instance tells you the answer to your original problem instance.
The obvious example is SAT (Boolean satisfiability'): here's a circuit with AND, OR and NOT gates, and a bunch of inputs and one output: is there a way of assigning TRUE and FALSE values to the inputs that makes the output be TRUE? This is NP-complete because you can take any other NP problem instance and encode it as a boolean circuit, with the inputs representing the witness:is there a witness that this problem instance has a YES answer’?
`As kangaroo mentioned, there are a few out there that would love to be solved in other than the brute force “proof” that “4 colors suffice”.’
Yeah, life sucks sometimes. But, on the other hand, we’ll have made some really important progress on something at which we’ve been very bad in the past, namely, determining lower bounds on algorithmic complexity. And, at least we’ll know that (say) trying to figure out ways to n-colour graphs in polynomial time is just a waste of effort. It’ll be something that only cranks waste their time at, like circle-squaring, angle-trisecting, perfect compression, perpetual motion machines, and so on.
Pat Cahalan • August 10, 2010 7:52 PM
So far, my favorite take on this has been Scott’s (http://scottaaronson.com/blog/?p=456) –
“If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.”
Translation: “He might have it, but I really doubt it.”
Pat Cahalan • August 10, 2010 7:55 PM
For the hard core math geeks out there, a more nuanced writeup:
http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
Liam • August 10, 2010 8:43 PM
Hmm.
I may have been wrong above when defending my definition of NP-Hard, apparently there’s huge confusion in the definition of the term. The definition used by my supervisors, textbooks and classes restricted it to decision problems, and defined NP-complete as the intersection of NP and NP-hard.
Apparently other books and researchers tend to use the term more loosely, including optimization problems and the like. The Wikipedia discussion page on NP-Hard is a turf war, with the current status putting my definition as an “alternative”. Anyone else run into this inconsistency?
Clive Robinson • August 11, 2010 3:13 AM
@ Ray, Moo,
Can I get away with “fortuitous accident”?
If not I’ll go for “the right not to” make my ears go red 😉
caf • August 11, 2010 4:05 AM
Michael Lynn: Actually, factoring is definitely in NP; this is trivial to show, because there is an obvious polynomial-time algorithm for testing a candidate solution: just multiply it out and compare to the original number.
What isn’t known is:
Also, I believe it has been shown that any proof that P = NP must be constructive – meaning that if it is ever proven, the proof will necessarily show a way to create a polynomial time solution to any NP-complete problem.
Michael Lynn • August 11, 2010 5:31 AM
@caf
Yeah, i know, but i was trying to avoid some levels for formalism in favor of making the crux of the question easier to understand for all. When i said that we’re not sure its in np, i meant of course strictly in np and not in p. That’s why i had my “shut up nerds” clause in there 😉
As for a proof of p == np needing to be constructive i think you might be right. Of course the most direct proof of any sort would be, like if you could find some solution in polynomial time (deterministic i mean) for an np complete problem then of course you could then use that to solve sat, then all the rest follow really easily. That said, even if they had a solution for sat in deterministic polynomial time tomorrow, you’d still probably have a bit of lead time before aes was done (hopefully because it would be some polynomial time algo that is still of a very large order of complexity).
Max • August 11, 2010 3:01 PM
@caf
Did you mean: “If factoring is in NPC, and if P!=NP, then factoring is secure forever against Turing machines.” (?)
Two things:
1. RSA was never proved to be equivalent to factoring, it’s considered to be easier (because factoring solves RSA trivially but not vice versa).
2. The consensus is that factoring is not in NPC class, because primality is proven to be in P, and these problems are very related. To be even more precise, almost all techniques used in cryptography are considered to be in P (RSA, DLOG, etc…). ZK is a clear exception.
ComplexityTheorist • August 11, 2010 6:09 PM
The P ?= NP question has nothing to do with cryptography.
If P=NP, you could still have a cipher that decrypts in linear time with the key and n^1000 time without the key. So it’s breakable in polynomial time, yet cryptographically secure.
If P != NP, then you could still have an NP-complete cipher that’s breakable in n^(1+n/1000) time. That’s cryptographically insecure, even though it takes more than polynomial time to break.
Plus, these classes deal with asymptotic key sizes and block sizes (the limit as the size goes to infinity), while crypto deals with specific, small sizes.
Plus, these classes deal with worst-case times, while crypto deals with average times.
Plus, the common crypto algorithms aren’t even NP-complete, so proving NP is harder than P still doesn’t tell whether they are in P or not.
So the P ?= NP question truly is irrelevant to cryptography.
Mark Wooding • August 12, 2010 7:52 AM
@ComplexityTheorist: `The P ?= NP question has nothing to do with cryptography.
If P=NP, you could still have a cipher that decrypts in linear time with the key and n^1000 time without the key. So it’s breakable in polynomial time, yet cryptographically secure.
If P != NP, then you could still have an NP-complete cipher that’s breakable in n^(1+n/1000) time. That’s cryptographically insecure, even though it takes more than polynomial time to break. […] Plus, these classes deal with worst-case times, while crypto deals with average times. So the P ?= NP question truly is irrelevant to cryptography.’
Complexity theory and cryptography are related, and P ?= NP is relevant but a long way from being decisive. As I mentioned earlier, P /= NP is /necessary/ but not /sufficient/ for computationally-secure cryptography in the sense usually used in current cryptographic research. For that, we need (at least) one-way functions, where /random/ instances are hard, not just worst-cast instances — and they must be hard in the sense that randomized polynomial-time machines have only negligible probability of guessing a right answer. So, in particular, we need that BPP /= NP, but even that isn’t sufficient. (Here, negligible' is a technical term, and meansless than any polynomial function, for sufficiently large problems’.)
I don’t think your objection is well-considered. The nice thing about thinking about cryptography in terms of polynomial-time machines and negligible functions is that the classes are closed under (randomized) polynomial-time reductions, i.e., reductions in BPP.
It’s been shown (see Oded Goldreich’s Foundations of Cryptography' for the distressingly turgid details) that you can build a pseudorandom permutation (crypto-research jargon forblock cipher’) out of a one-way function with the following security property: if any algorithm can distinguish the pseudorandom permutation from a really random permutation, with non-negligible `advantage’, then you can, using only polynomially more effort, invert the one-way function, again with non-negligible advantage.
These kinds of results pervade modern cryptography. Some of them, like the one I’ve just described, actually have rather inefficient reductions — the reductions take quite a lot of effort (the polynomials have high degree) and the probability drops off quite sharply. It’s all held together by the magic of the asymptotics: decide how much adversarial disadvantage you want, and choose a security parameter that’s big enough. The asymptotics guarantee that it exists. And that’s why the polynomial/not-polynomial distinction is important. If your one-way function (say) started with an O(n^1000) adversarial disadvantage, an inefficient reduction from your final protocol might fritter it all away, and you end up with no security at all at the end. But if it has an n^(1 + O(n)) reduction, then you’ll /always/ be able to choose n big enough to put any amount of clear air you like between you and the adversary. Of course, you may not like the size of the system you end up with. But at least it’s secure.
Currently, though, this is all built on sand. One-way functions might not exist at all. Separating P and NP is a really good first step, though.
`Plus, these classes deal with asymptotic key sizes and block sizes (the limit as the size goes to infinity), while crypto deals with specific, small sizes.’
Yes, this is my objection to all of this. The asymptotic approach I’ve described above is great for theoretical results: you can build block ciphers, symmetric encryption schemes, message authentication codes, and much cleverer things, all out of one-way functions and sellotape. But actually the things we start from in symmetric cryptography are block ciphers like AES or stream ciphers like Salsa20, and they have an inconvenient property: they’re /fixed/. AES has a 128-bit block size and a 256-bit key, whether you like it or not. There just isn’t a scaled-up version with a 3-million-bit key. So, for practical purposes, asymptotic security results are close to worthless.
Thanks to work started by Bellare, Kilian and Rogaway, we have a rich body of cryptography literature providing concrete reductions which work for fixed-sized things that we’ve actually got, like AES and SHA-256. This vein of research is also built on sand. And whether P = NP really isn’t relevant here, because it’s an asymptotic statement. What we really want to know is: can we build a function which takes at most n steps to compute but /provably/ takes at least N >> n steps to invert with probability better than (some tiny) epsilon? Can we do something similar for block ciphers, or stream ciphers?
On the other hand, currently, we seem to suck hopelessly at determining lower bounds on computational complexity. Life is easier if we try to think about asymptotic complexity classes, because the asymptotics hide an enormous number of details about performance models) but we suck at separating those too. Dealing with individual, specific, concrete problems requires more realistic (and detailed) computational performance models, and that’s going to be really hard.
Showing that P /= NP is a small step. But it’s a step in the /right/ direction, so we should be grateful for that when it happens.
(Sorry this was a bit long.)
Thomas Jones • August 12, 2010 10:56 AM
@Ciaran McNulty even if P != NP we won’t know for sure that factoring is not in P since it’s not an NP-complete problem.
Mark Wooding • August 12, 2010 11:37 AM
@Thomas Jones: `even if P != NP we won’t know for sure that factoring is not in P since it’s not an NP-complete problem.’
Nope, that’s not proven either. We do know that factoring is in NP cap co-NP, so it’d be a big surprise if it’s NP-complete, since that’d show that NP = co-NP, but we just don’t know either way.
David Schwartz • August 13, 2010 2:00 AM
The simplest way to explain why P ?= NP has no direct bearing on modern cryptography is this:
Cryptography is based on encryption being easy, decryption with the key being easy, and decryption without the key being hard. Here ‘easy’ means that it can be done without too much difficulty on actual machines we have developed and ‘hard’ means that it cannot be done at all, for practical purposes, without performing more calculations than we expect anyone to be able to perform.
The P ?= NP problem is about whether problems are ‘easy’ or ‘hard’. Problems that are ‘easy’ may actually be impossible to do for practical purposes, requiring more calculations than can be done if every particle in the universe were a computer doing a trillion calculations per second for the suspected age of the universe. Problems that are ‘hard’ may actually be trivial to do, requiring only a few calculations.
An algorithm that breaks all known cryptographic algorithms in polynomial time (thus ‘easy’) would have no effect on the security of known cryptographic algorithms if the number of calculations it required to break actual key sizes in use was, say, 10^100.
Winter • August 13, 2010 5:27 AM
@David Schwartz
Another way to look at P?=NP and cryptography:
If P != NP, cheap cryptography can always outrun resourceful brute force decryption as breaking cost rises exponentially while en/decrypting only polynomially
If P=NP, a resourceful opponent can always outrun a poor encrypter
Eg, often adding 1 bit increases en/decryption costs to (n+1)^K while it doubles the cost of attack. If n > K, you quickly get an advatage over the attacker.
Absolute costs do matter, but it is the message sender that selects the method. She can always look for a cryptographic system that has K in her advantage.
proof • August 13, 2010 4:11 PM
it seems in fact the proof is flawed, but let the experts decide,
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comments
David Thornley • August 13, 2010 5:06 PM
@Daniel Schwartz: The importance that P=NP would have is in how we determine trust in cipher systems.
We trust AES-256 because of two things. First, we know of no cracks (this is admittedly speculative), and therefore the only way anybody’s come up with to break it is brute force. Second, it physically cannot be brute-forced with the resources of only one galaxy. Even if some quantum trickery reduces the effective keylength in half, it’s still impossible to brute-force a 128-bit key with the resources of only one solar system.
If P=NP, we know there’s a way to crack it without the need for brute force. The standard way (based on the proof) may be infeasible in the same way as brute force, but now we know that we don’t need brute force. It’s like a crack reducing complexity to something like 2^192; it reduces our confidence in the cipher.
ComplexityTheorist • August 16, 2010 12:15 PM
@David Thornley “If P=NP, we know there’s a way to crack it [AES-256] without the need for brute force”.
That’s not true. Even if P=NP, there may still be no algorithm for breaking AES-256 other than brute force.
If P=NP, then there’s a polytime algorithm for breaking AES-K, for keys of size K, that’s polynomial in the limit as K goes to infinity. But it’s possible that this magic algorithm works by reducing the AES-K problem to a small set of AES-256 problems, breaking each of those subproblems by brute force, then combining their answers to get the answer to the original AES-K problem. Such an algorithm tells us nothing new about AES-256.
So even if P=NP, it’s still possible that AES-256 has no breaks other than brute force. It’s even possible that AES-trillion has no breaks other than brute force. All P=NP would tell us is that we’ll have something other than brute force for key lengths above SOME unknown threshold.
[p.s. Yes, I know AES-K technically doesn’t exist for large K; obviously I mean Rijndael-K for any K for which AES-K isn’t defined]
ComplexityTheorist • August 16, 2010 12:28 PM
Actually, AES-K is already known to be breakable in polynomial time. That’s because, in the limit as K goes to infinity, the block size remains constant. So AES-K is in P. Which, of course, is completely irrelevant when we’re talking about cryptographic security.
ComplexityTheorist • August 16, 2010 12:33 PM
Sorry, AES-K is in RP. I don’t know if it’s in P. But the point remains: the fixed block size is a problem as the key length goes to infinity, but that has no effect on the security of any given size like AES-256.
ComplexityTheorist • August 16, 2010 2:23 PM
Here’s the details of why we know that AES can be broken in polynomial time. And why that’s irrelevant to whether it’s secure or not.
Let AES-K be Rijndael with a K-bit key and 128-bit block. Let AES-K-ECB and AES-K-CTR be Electronic Codebook mode and Counter mode, respectively.
For a chosen-plaintext attack on AES-K-ECB, the problem is clearly in P. In fact, the attacker can succeed in time and space linear in the time it takes to do ordinary encryption/decryption with the key.
That’s because AES-K-ECB is a simple substitution cipher on an alphabet of 2^128 “letters”. So it can be broken with 2^128 chosen plaintexts. And 2^128 is merely O(1), because it doesn’t depend on K. The “key” you find is a table with 2^128 entries, which is merely O(1) space. So AES-K-ECB is in P.
If you prefer counter mode, AES-K-CTR uses a counter the size of the block, so the counter wraps around every 2^128 blocks, so you need only 2^256 chosen plaintext blocks to completely break it. So again, AES is in P.
This is a great illustration of how the P ?= NP question truly isn’t relevant for cryptography. Cryptographers want to know whether AES-256-CTR is secure. Many people bet it is. But AES-K-CTR can be broken in polynomial time, and so is in P. And AES-256-CTR isn’t in any complexity class, because classes like P and NP need a “size” that goes to infinity.
So from a complexity theory viewpoint, AES is no different from the decoder ring you get in a cereal box.
Spudd86 • August 17, 2010 12:25 PM
@flatline
IIRC integer factorization is known to NOT be NP-complete, it’s just no known if it’s in P. It may be in NP – P – NP-complete (That is not in P, not NP-complete, but still in NP)
Spudd86 • August 17, 2010 12:28 PM
@Foo NP means non-deterministic polynomial, not “Not Polynomial”, these are very different things.
Pelle in Uppsala • August 21, 2010 11:19 AM
I think the proof is OK.
But it is not a mathematical proof,
because it relies on things we observe in nature.
So therefore, there will be no 1M$.
Tom • March 4, 2011 11:35 PM
Brucer:
I found an interesting posting on a blog. Do you have a comment on this ?
Bob • March 9, 2018 5:32 AM
“the paper is by a respected researcher — and not a crank” – OK, the solution is more likely to be obtained by a professional researcher, but I can’t support the use of the word “crank” to tar all amateur mathematicians with the same tinfoil brush.
Most amateur mathematicians like myself, don’t believe the world is flat or that the government is bombarding us with mind-control chemicals, we just like to enjoy having a go at the mathematical problems of the day over a cup of tea or, more likely, a beer or two. C’mon Bruce, don’t be so hard, it makes us feel .. er .. cranky!
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
barbie • August 9, 2010 3:07 PM
Most proofs that are that complex usually have some minor flaws, but not necessarily fatal ones.
Any reason you think this one is flawed ? and do you mean typo-flawed, or major-flawed ?