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.
P vs. NP for dummies
Can anyone explain what all the fuss is about ?
Its strongly related to the "CS" vs "IT" division amongst "computer people". Its hard to find a topic that more strongly shows the separation.
The "IT" guys simply don't care (look at many of the posts in this article) but for the "CS" guys its proof would be pretty close to the ultimate "super bowl win" or "moon landing" or "date with a girl" moment.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
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.
The P = NP problem is one of the most important open questions in complexity theory, and a solution to it would have broad implications. For example, if P!=NP, then we would have provably secure cryptography without having to assume as much as we currently do (in layman's terms: cryptography would be a bit easier to "get right"). If P=NP, then a lot of important problems could be solved efficiently (e.g. the travelling salesman problem, the place-and-route problems, etc.). Additionally, a P!=NP proof would likely involve yet-unknown techniques of proving lower bounds on the complexity of problems, as well as providing a straightforward method of proving lower bounds on the complexity of some problems.
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.
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!
Its the basis of the argument that our CS people gave us as to why a natural language recognition system could not be developed. So a couple of flight control (mechanical) engineers sat down and wrote one.
An excellent example of science "vs" engineering.
The scientists say a theoretically perfect system cannot be made. Also true that the abstract concept of a metal cube exactly one inch on a side cannot exist, because of various quantum and thermodynamic reasons there will always exist a variation somewhere deep in the decimal points.
The engineers, however, are perfectly able to make ones that "work well enough".
The hop from theory to engineering that happens with P=NP is almost as funny/interesting to talk about as the second hop on the same topic from engineering to mass media.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
It was a trick question meant to test how many people were paying attention in their theoretical CS courses.
Palm trees and 8
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'
I've been in this business since the 1980s. When I started, there were proportionately a lot more math geeks in software than there are today, but by the early 90s there wouldn't have been enough math geeks in all the world to do the work that needed to be done. The people who came into the business had the attitude that complexity and computation theory were just a lot of ivory tower rubbish.
There was a certain validity to this attitude. There was ton of work to be done, but almost all of it amounted to assembling endless variations of the same old kinds applications but in new contexts. It was like snapping together different Lego projects. The mathematically difficult work had already been done for the people engaged in that work, and so their intellectual focus shifted to issues of craft and project management, which were by no means trivial things. Some of us kept algorithm books handy for that odd job where the library routines didn't quite do, but we didn't really need much math. We just needed a rough grasp of O notation and the ability to translate pseudocode into C. Most software guys didn't even go that far. They didn't have *any* math books or references on their shelves, just big, fat tutorial books on vendor provided solutions or architectural philosophy.
Then came the Internet.
A lot of Internet related software falls into the Lego Architecture class, but given a world of data that are interconnected, there's more need than ever for people who can create *new* algorithms that can squeeze gems of value out of that mountain of data quicker than the Universe will perish from heat death. Companies like Google or Facebook or LinkedIn can't just slap a Java front end onto an Oracle database. They have to create new ways to structure and process volumes of data magnitudes beyond anything that existed in the early 1990s.
Fundamental (in the sense of "foundational" rather than "beginner's") CS is once again very practical knowledge to have.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.