Slashdot Mirror
Forty Years of P=NP?
An anonymous reader writes "In the afternoon of May 4, 1971, at the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard. 'The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.'
And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history.
Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today."
Alan Cobham wrote a paper defining the complexity classes L and L+. These are exactly P and NP. He may also have originated the concept of defining the complexity of an algorithm as a function of the input size.
Alan did not however show that there were a large number of problems which were in reducible to L+
15 years of developing software and I still don't know what P vs. NP means.
Sad, sad old hacker.
YP != MP
In Soviet Russia, Chuck Norris will still kick your ass.
Slashdot seems to have a hard-on for this topic:
http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP
http://science.slashdot.org/story/11/01/20/1546206/Polynomial-Time-Code-For-3-SAT-Released-PNP
http://science.slashdot.org/story/11/02/28/149244/No-P--NP-Proof-After-All?from=rss
http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof
http://science.slashdot.org/story/10/09/10/1847245/How-the-Web-Rallied-To-Review-the-P--NP-Claim
Can anyone explain what all the fuss is about ?
Are you the only person who couldn't be bothered to look it up?
http://en.wikipedia.org/wiki/P_versus_NP_problem
am I the only person who does not get what this means?
The most non-mathematical way to express it, probably somewhat innacurately, is the fastest way to figure out if you can learn what "p=np" means is for you to figure out what "p=np" means and then see how long it took.
Its also used as a stereotypical filter... If you know what it is, you're somewhere on the "computer science" path. If you don't, even if you don't know it, you're on the "IT" "IS" or "code monkey" path. It's almost as accurate as asking someone if they've heard of a programmer named "Knuth".
If you're involved in any problems similar to any on this list:
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
and you've ever thought about scalability, then you're at least on the path to understanding P=NP
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
P vs. NP for dummies
P=NP. The easy way to understand NP (non-deterministic polynomial time) are problems that can be solved with age old the guess and check method. P=NP roughly implies that any problem that can be solved with guess and check can also be solved deterministically.
Actually, it's not an iff. If P=0 then P=NP no matter the value of N. ;)
Score: i, Imaginary
Do you like to have your files, HTTPS sessions, etc encrypted? Yes? You want it to be hard to crack that encryption? Yes? Then you care that P != NP.
So, what's happened since then? We're still a long way from resolving P ?= NP. There's been a lot of success showing some techniques won't work. The fact that P^A != NP^A for some oracle A and P^B = NP^B for some other oracle B shows that a lot of possible paths simply won't work. Thus for example, there can't be any clever but essentially straightforward reduction of NP problems to P because then we would have P^A=NP^A for all oracles. Similar remarks apply to the so-called natural proof barrier.
There's been more success with related problems. In the last few years, the apparent size of P has grown. Thus, Agrawal et. al. showed that primality testing is in P http://en.wikipedia.org/wiki/AKS_algorithm and there's been a lot of success with taking randomized algorithms that lie in BPP and producing non-randomized versions that are in P. This had lead many to suspect that in fact P=BPP. Most recently there's been some very good work with circuit bounds. Ryan Williams has done very recent technical work showing that NEXP and ACC are not equal. This work seems to get around the natural proof barriers. There's also been some work relating complexity questions to algebraic geometry and the permanent of a matrix. ( No, that's not a typo- http://en.wikipedia.org/wiki/Permanent ). So there's a lot of interesting work going on, but it seems that we're pretty far from actually resolving whether P != NP. I suspect that we'll prove the weaker result that P != PSPACE before we resolve the stronger claim that P != NP.
Do you like to have your files, HTTPS sessions, etc encrypted? Yes? You want it to be hard to crack that encryption? Yes? Then you care that P != NP.
Although note that encryption being hard is generally a much stronger claim than P != NP. All known encryption systems that rely on complexity conjectures need stronger claims than P!=NP. Thus for example many rely on the difficulty of factoring integers into primes. It is possible (although it seems unlikely) that P != NP but factoring is still in P. The reason to care about P ?= NP in an encryption context is that if P = NP then encryption definitely doesn't work. But the other direction isn't necessarily the case.
Wow so close to history TWICE that day.
Since I was only ten years old at the time I remember the the shootings but not this bit o' history. I did live around that area, I do know that hotel did turn really sleazy just a few years after that symposium.
Coincidence?...
God: When you do things right, people won't be sure you've done anything at all.
All known encryption systems that rely on complexity conjectures need stronger claims than P!=NP.
This is not technically true; some cryptosystems based on lattice problems have security reductions to NP-hard problems and ultimately rely only on P!=NP.
Palm trees and 8
There was a question, in a round about and not obvious way, asked us to prove P = NP. Dirtiest most evil trick question I've ever encountered.
Wow, that's a level of stupid I haven't even seen on 4chan in a while...
weinersmith
NP-hard is different than NP-complete.
Imagine if you weren't allowed to use roads because a bus company complained about your driving 3 times. --skunkpussy
The reason to care about P ?= NP in an encryption context is that if P = NP then encryption definitely doesn't work.
Not true at all. Encryption works if, on average, it takes too long to break it using current technology for the data to be useful once its finally broke. Its an engineering balance, not a theoretical process.
P = NP is a scalability problem where it seems a very small amount of work and very small amount of key is very hard to break.
Something like DES scaled down to 8 bit keys (uh, good luck scaling the s-boxes down, but you get the general idea) is a horrible engineering decision regardless of how scalable the theoretical design is. One of 256 keys will give you your plain text english words back.
If P=NP the days of using a simple algorithm with a tiny key to protect huge amounts of data is over, but that doesn't mean crypto is dead. It just means maybe you need billion bit keys for an engineering win instead of thousand bit keys for an engineering win, and you'll have to pay more attention to improvements in processor speed and parallel processing. It hardly means its "magically" dead.
Think of it in chemical terms : proving N=NP is a chemist proving a formula exists. "breaking crypto" is more like a chemical engineer figuring the appropriate limiting reagent and reaction rate kinetics using the previously mentioned formula as a tool. If the chemist figures out a new formula, worst case scenario is the engineer has some late nights of work, not unemployment.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
When I took a graduate level compilers course, the professor gave a quiz early in the semester on writing CFGs. One of the questions was essentially to write a CFG for this language:
a^n b^n c^n
Quite a few people had trouble finding the right answer...
Palm trees and 8
I looked in to this discussion just because I wanted to see what the hardcore science/math nerds were saying, and instead I get a dozen posts asking, "What the hell is P=NP, LOL." Time was, you could look into math threads on Slashdot and see graduate students talking shop. Even if I didn't understand half of what they said, it was still enlightening.
Shutting down free speech with violence isn't fighting fascism. It IS fascism!
One my think some Wikipedia articles need a tl;dr
This guy did it pretty well.
My ignorance is just as good as your knowledge.
Provably secure cryptography is about scalability, and proving the infeasibility of solving particular problems. Unlike many block ciphers, whose security is stated in terms of statistical tests, cryptosystems like RSA and ElGamal have security stated in terms of reductions to problems that are believed to be infeasible (and if we could show P!=NP, then we could have cryptosystems that are reducible to problems that are infeasible). Public key cryptography is not an engineering problem, it is a theoretical CS (or perhaps we can just say "math") problem.
Palm trees and 8
Did it turn out to be a trick question or did he really want a^nb^n? The former is very evil while the latter I guess I can understand.
The graduate students are still asleep :)
It was a trick question meant to test how many people were paying attention in their theoretical CS courses.
Palm trees and 8
D'oh! Maybe that's why people are having such a hard time with it. Should have subtracted P from both sides getting P(N-1)=0. OK, solving P=NP took me two tries - Now I understand the debate.
He's getting rather old, but he's a good mouse.
This is a real world example I've seen a dozen times. Given a spec that requires a parser, the CS type will come up with a complicated (to outsiders) solution that few people can understand but works perfectly. The IT type will not recognize that it is a parser, does not know what a parser is, and will implement a very buggy "solution" with regexps (cf. the MySpace XSS fiasco from a few years back).
Oh who am I kidding; there is no such thing as a spec. I've never seen an actual one in the enterprise.
Every time there is a P vs NP story on slashdot, invariably there is at least one person to make a comment like this... and every time, I see comments like this modded up as amusing. Am I the only person on slashdot who has long since ceased to find it funny?
'P' stands for "polynomial", and 'N' stands for non-deterministic. Neither side of the equals sign actually represents any single value... rather, they each represent what are typically considered to be separate classes of problems.
To assert that P = NP is to assert that problems which are provably NP hard can actually be solved in polynomial time on the same architecture on which they are supposed to be NP, and therefore NP does not, in strictest sense, exist.
It would spell the end of virtually all currently used forms of encryption, but would open up entirely new types of problems that we could get computers to solve that are currently considered wholly infeasible.
Please... how hard is it to Google?
File under 'M' for 'Manic ranting'
Actually, that's not true... It can take far less time to construct a method for solving a problem than it can to actually solve it, and analysis of the method constructed can readily reveal the time that the method actually takes to utilize, again in far less time than it actually takes to solve the problem at hand.
File under 'M' for 'Manic ranting'
What the hell? It was Stephen Cook when I took his classes back in the nineties.
Hey, /. editors, how is that guy, what's his name, Commander TacoBell doing?
You can't handle the truth.
NP-complete is by definition the intersection between NP and NP-hard. There are for sure NP-hard problems, which are not in NP, so you are right that the sets are not identical. I believe the halting problem is NP-hard, but it certainly isn't NP-complete.
Do you care about the security of your wireless mouse?
Pass it on down, dude, don't sit there slobbering on the end.
I bought this house and you know I'm boss
Ain't no h'aint gonna run me off
Am I the only person on slashdot who has long since ceased to find it funny?
No. It was funny once, a very long time ago. Perhaps. Well maybe slightly amusing a very long time ago. It's getting pretty annoying these days.
SJW n. One who posts facts.
So if I find an O(n^{100000th Ackermann number})
algorithm for factoring integers, it means encryption is suddenly unsafe? Your understanding of this issue is very flawed.
Le français vous intéresse?
No, but I think a Beowulf cluster of those posts would be absolutely hilarious!
What a fool believes, he sees, no wise man has the power to reason away.
I used to think that, too, but actually the grandparent is right: all cryptosystems invented so far rely on something more than P!=NP.
It's true that some cryptosystems reduce to NP-hard problems, but that doesn't mean they rely solely on P!=NP to be secure.
The problem is that when you have a NP-hard problem, that doesn't mean that all its instances are hard to solve. For a cryptosystem based on NP-hardness, this means that not all messages are hard to decode, only that there exists at least one message that is hard to decode. To prove the system is really secure, you need to rely on some other assumption, or you'd need to find a way to use only instances of the NP-hard problem that are actually hard, and there's no known way to do that yet.
Also, lattice-based cryptography is not known to be NP-hard: as far as I understand, to break it you must find an approximate solution to SVP, you don't need to solve it exactly (which would be NP-hard). Still, it's believed that lattice-based cryptography it's harder to break than factoring.
For more information: http://stackoverflow.com/questions/311064/are-there-public-key-cryptography-algorithms-that-are-provably-np-hard-to-defeat
the notation itself is ambiguous, but i suppose you could do it (what we would consider) wrong, and define the ^ operator to only take one token.
I've found a very nice solution to this problem. Unfortunately this comment box is too small to contain it.
I was at a talk by Stephen Cook once and he actually set proving P != NP or P = NP as an undergrad student project. Shows people then didn't fully appreciate how difficult it was. Perhaps he spent a week trying to solve it and felt close enough to be sure it could be done.
You've probably noticed that people's noses get bigger as they get older. That's because old people are huge liars.
Everything practical is an engineering problem. Factoring could be in P and still be infeasible, for many different reasons. Factoring could be in NP and stil be feasible, for many different reasons. P vs NP is just one important factor in the feasiblity of an attack.
Also, there's no such thing as a "provably secure" cryptosystem - what rubbish! The very idea of "provably secure" is wrong-headed in any sort of security (digital or phisical).
(BTW, the NSA has been deprecating product-of-primes based crypto for many years now, and it shouldn't be used for new work).
Socialism: a lie told by totalitarians and believed by fools.
Surely, but he was using the terms interchangeably. They're really not. Entirely different kind of proofs. Similar, but weaker.
Imagine if you weren't allowed to use roads because a bus company complained about your driving 3 times. --skunkpussy
I believe the halting problem is NP-hard
No. The halting problem is wholly insoluble since if a solution existed, we could trivially construct code that only halted if it didn't halt and vice versa: a complete contradiction in terms. NP-hard problems can all be solved with sufficient application of computing power; you might have to wait a long time, but they are still properly algorithmic. (The "P=NP?" question is about whether efficient algorithms exist for solving a very large class of problems, or whether they just have to be brute-forced.)
"Little does he know, but there is no 'I' in 'Idiot'!"
Everything practical is an engineering problem
The engineering problem with theoretical cryptography is in implementing it, not in designing it.
Factoring could be in P and still be infeasible
That depends on your definition of "infeasible."
Factoring could be in NP and stil be feasible, for many different reasons
Only if factoring is also in P, or if you have some other definition of "feasible."
Also, there's no such thing as a "provably secure" cryptosystem - what rubbish
"Provably secure" has a specific and well understood meaning in the cryptography research community. It means that if a cryptosystem can be cracked in polynomial time in its security parameter, then a (assumed to be) hard problem could also be solved in polynomial time. If one could show that there is no polynomial time algorithm for the RSA problem, then the RSA cryptosystem would be secure against any polynomial time attack. Since the commonly understood definition of "feasible" is "polynomial time," this would mean there is no feasible attack on RSA.
(BTW, the NSA has been deprecating product-of-primes based crypto for many years now, and it shouldn't be used for new work).
Actually, the NSA has been deprecating all cryptography based on the hardness of problems on the multiplicative groups of integers modulo X, which includes RSA and the non-elliptic curve versions of DH and ElGamal. The reason for this is the necessity of large public keys to maintain the same margin of security as a symmetric cipher, due to the state of the art attacks on the factorization problem (GNFS) and the discrete logarithm problem, which run in subexponential (but still superpolynomial) time. The NSA has been pushing for elliptic curve cryptography because of the promise of smaller key sizes, although the attacks on those cryptosystems are also subexponential (but square root instead of cube root).
Palm trees and 8
Computer Science: An Overview by Brookshear
http://www.amazon.com/gp/product/0132569035/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0201781301&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=156PMT03KVNBZ06TDF4D
Get it, and you can thank me later.
I'm pretty sure that if you prove P=NP, that there may be consequences. It you are very, very lucky, Bob from the Laundry will pop by and arrange for a new career for you, or at least keep your brain from being eaten.
... things ... that cast shadows on the walls of Plato's cave may make them pay attention. This is, however, a dangerous process, because many of the shadow-casters are unclear on the distinction between pay attention and free lunch buffet here. [1]
If you're not so lucky, well, pointing a loaded theorem at the
1. http://en.wikipedia.org/wiki/Charles_Stross#The_.22Bob_Howard_.E2.80.94_Laundry.22_series
The engineering problem with theoretical cryptography is in implementing it, not in designing it.
Of course it is - that's the important part.
No one ever attacks a secure system by attacking the math of the crypto algorithm (unless the "algorithm" is only a marketing ploy). You attack the weak points of the system: the key management, or the users. You decrypt Osama's hard drive by waiting for him to decrypt it, then kicking down the door and shooting him in the face.
Factoring could be in P and still be infeasible.
That depends on your definition of "infeasible."
Of course it does. Real world computers behave differently from whiteboards. Polynomial time can still be really bad, or have unattainable resource requirements (even if you measure computer time in acre-weeks).
Factoring could be in NP and stil be feasible, for many different reasons
Only if factoring is also in P, or if you have some other definition of "feasible."
http://xkcd.com/538/ or if the key size is too small, or if the user clicks on CoolProgram.exe, or one of the many other attacks that ignore the math work.
"Provably secure" has a specific and well understood meaning in the cryptography research community.
Funny how security professional constantly rail against the very idea. "provably NP-complete", sure, but "secure"? Nonsense.
Socialism: a lie told by totalitarians and believed by fools.
Funny how security professional constantly rail against the very idea. "provably NP-complete", sure, but "secure"? Nonsense.
You yourself said it:
No one ever attacks a secure system by attacking the math of the crypto algorithm
The math is what is provably secure, and that is what cryptography is about. If you implement a cipher badly, it is not the cipher that is insecure, it is your implementation of it (or perhaps we might say that you did not really implement the cipher; Sony was not really using ECDSA for the PS3, since ECDSA requires a random number to be generated for every signature).
As for security professionals...well, I have spoken to many of them, and the almost universal answer I have received is this: security engineering is not cryptography, cryptography is not security engineering. Cryptography is a piece of the security engineering puzzle, and provably secure cryptography is a piece of that piece, but there is more to security engineering than that. The security of a system often goes beyond the ability of an adversary to guess a message or compute a forged signature; cryptography is not the be-all and end-all of security engineering.
http://xkcd.com/538/ or if the key size is too small, or if the user clicks on CoolProgram.exe, or one of the many other attacks that ignore the math work.
None of this has anything to do with cryptography. Small key sizes are irrelevant in security proofs; the point of the proof is that you can always select a key size large enough to protect against an adversary, without incurring an infeasible computational cost for encryption/decryption (or whatever your cryptographic primitive happens to be). Determining a proper key size -- one that is small enough to be practical but large enough to maintain a particular security margin -- is an implementation issue, and falls outside the scope of theoretical cryptography. Beating someone with a wrench falls way outside of the scope of cryptography (even applied cryptography) and is essentially in the same category as a user downloading a trojan horse: users betraying their own security. A security proof has the underlying assumption that the users are knowledgeable and will not undermine their own security (this is a common point of contention when it comes to deploying cryptosystems in "the real world," since most computer users are not knowledgeable and are often unaware that they are undermining their own security; this is beyond what cryptography alone can provide an answer for).
Ultimately, the point is that cryptography can only offer answers up to a particular point, and "security" in the context of cryptography is bounded by that point. What cryptographic security proofs offer is assurance that a cryptosystem is not the weak link in a large security system; security engineers can spend their time worrying about other problems (composing different components without compromising security, ensuring that users do not leak keys, etc.) and not worrying about attacks on the cryptosystem itself (at least that is the idea; in practice, the difficulty of proving a lower bound on a problem's complexity can result in situations like the one facing RSA, where key sizes wind up becoming larger and larger to the point where the system begins to lose its practical advantage).
Palm trees and 8
There is no requirement for the problem to have a solution. Even if there is no way to test if an input is in a set L, it may still be the case that L is hard. In order for L to be NP-hard, there has to be a polynomial time algorithm that can reduce any NP problem to L. If you take L to be the halting question, then such a reduction is trivial. Just simulate the nondeterministic TM with all possible choices for the nondeterministic parts until you find the one that makes it halt and accept. If no such choices exist, the simulation will run for ever. Hence, it will halt iff the input for the reduction was in the NP set that we were interested in.
Do you care about the security of your wireless mouse?