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.
all the fake (stingy fatal) 'math, science' & religion' in the wwworld, will not cipher to any reasonable conclusions, because of failures to acknowledge the progression of our dna, increased conscience & awareness, new babys etc... makes it all look like the failing fictional foibles of flashy fake neogods, losing their lightning rods.
No shit. Just like the only way to solve the P=FP problem is to post a first post.
YP != MP
In Soviet Russia, Chuck Norris will still kick your ass.
then add at least a pointer to the source.
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
Exactly - Divide both sides by 'P' and it reduces to 'N=1'. So, P=NP iff N=1. People who spend so long on this debate must not be very good at math... =)
He's getting rather old, but he's a good mouse.
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
10 out of 10 Space Nutters agree, we only have computers because of the Apollo missions. There was no theoretical or practical groundwork done prior to large rockets.
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.
That's the easy part - the 'age old question' is how can we write a computer program that can find ALL the solutions to this problem in a reasonable amount of time. Verifying that 9, or 2, or pi, is easy, but finding a true solution to the equation is what this deals with.
Your math gets a failing grade. You missed the solution where P=0 without any constraint on N.
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.
Huh. I drove by there any number of times while I lived in Cleveland. I had no idea that place was where the conference took place. Instead of a motel, I think it's now a real-world Bachelor Arms, complete with long-term stay efficiencies and rent discounts.
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
Sigh....
It's actually a pretty simple concept but you do need to be familiar with the jargon:
P and NP are "complexity classes" meaning they're short hand for a formal definition of large groups of computable problems. There are many complexity classes but P and NP are two particularly important ones because modern cryptography is based on the premis that they are not the same (which seems likely even though it has never been proven true).
Modern cryptographic approaches require the concept of a "trap door" function. That is it's sufficiently more computationally costly to generate a valid solution than it is to verify that the solution is correct. This means that if P!=NP you can have your decryption algorithm be P and you key generation algorithm be NP, and in order to crack a key of any given complexity, the cracking computer would need to be exponentially more powerful than than was necessary to use the key (so you'd need a super computer to crack your cell phone's encryption for example).
If however P=NP than there's no way to guarantee that your cryptography program can't be cracked on a computer only marginally more powerful than the one using the key (say you need an i7 to crack the keys that were reasonable on an i5)
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!
some cryptosystems based on lattice problems have security reductions to NP-hard problems and ultimately rely only on P!=NP.
But then again, NP-hardness only means that for every n, there is an m > n such that a "hard" instance of the problem of size m exists. There are NP-hard but insecure cryptosystems.
before it's all gone already? the americannex dream is finally realized. plus, not only completely reviving our god blessed economy, each citizen can now afford enough weaponry & personal spy stuff so that atmospheric & other atmostfearinc terrorism will continue to be our #1 chosen businesses. & now recreation (or continued decreation) for centuries to come. it's not just a dream after all.
after all, we've all paid in with big parts of our lives, so far. after disarming, there'll be lots of extra fake dough everywhere right away. if we had prayers, this would be it?
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.
40 years of these exact same jokes, and the exact same corrections, every time Slashdot runs a story on P and NP....
- curmudgeon
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'
No, not because i understand the P NP problem and am a fan. Just because i live relatively close to that
Stouffers.
K
And this right here is a perfect summation of why negroids never excel in the maths or sciences.
NP-Complete is the intersection of NP and NP-Hard.
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?
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?
Now that's a tautology
(I'm a grad student in CS who should be writing a summary on Toda's theorem right now, and instead am looking at slashdot. God dammit.)
An intuitive way to look at NP problems is that you're asking whether a solution exists to some other problem that's easy to verify. It's easy to look at a boolean formula of ones and zeroes, joined by ands, ors, and nots, and tell whether it comes out to true. It's very hard, however, to replace the ones and zeroes with variables, and tell whether any assignment of those variables to ones and zeros will result in a formula that comes out true.
The analogy of songwriting is illustrative. I can tell if a song is good or bad pretty easily. But that doesn't mean I can write a good song. Where do I start? To write the song, I have to choose from all the different notes, then choose another note out of all the possible notes, and so on. Once I've come up with a song, I can sit back and judge its quality (relatively) easily.
Now, one solution is to generate all possible songs, and when I hit upon one that's good, record it and become a rock start. But generating all possible songs, then judging them, takes a very long time. (And if I add a new instrument to the mix, it will at least double the amount of work I have to do, if I'm generating all songs.)
But a theoretical NP machine generates "songs" as fast as it can judge "songs". (We're not really talking about songs, we're talking about satisfying assignments to boolean formulas.)
Many AI problems are NP-complete, which is why AI classes are all about heuristics. So if anyone ever comes up with P = NP, find John Connor.
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
http://blog.computationalcomplexity.org/2011/05/forty-years-of-p-v-np.html
It seems we've made tremendous advances in plagiarism though.
says P=NP guy.
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
This was ripped from the following original source:
http://blog.computationalcomplexity.org/2011/05/forty-years-of-p-v-np.html
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?