Forty Years of P=NP? 222
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."
Actual origins are even earlier (Score:2, Informative)
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+
Re:P=PN (Score:4, Informative)
In simple terms, problems in P can be solved in a polynomial number of operations on a computer with one processor (or with a constant number of processors), and problems in NP can be solved in a polynomial number of operations on a computer with an unbounded number of processors (or in other words, a computer which can explore an unbounded number of solutions at the same time). This is not the most rigorous definition of the classes, but it is one of the more intuitive.
The problem is this: is P a proper subclass of NP, or are there problems in NP which are not in P? The Cook-Levin theorem established the existence of "NP complete" problems, which are those which are in P if and only if P = NP.
Re:So? (Score:5, Informative)
P vs. NP for dummies [scottaaronson.com]
What has happened since then (Score:4, Informative)
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 [wikipedia.org] 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 [wikipedia.org] ). 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.
Re:P=PN (Score:5, Informative)
My computer science is rusty, but essentially it wants to know if polynomial time solution algorithms (n^2, n^3, ..., n^c: where c is constant) exist for EVERY problem that is verifiable (solution checkable) ALSO in polynomial time.
Classic example, traveling salesman problem. Imagine you have to visit 5 cities, find the ordering of visits that yields the lowest total distance traveled. This problem is NP hard, thus it requires exhaustive search ( 5! solutions => n! time) to find an optimal solution. Verification of an optimal solution can be done in polynomial time (i.e. you already have the answer).
The cool part about P=NP, is that if ONE algorithm is found that solves an NP hard problem in polynomial time, ALL problems are solvable. You can map one sort of NP problem (e.g. traveling salesman), to another sort (e.g. 3-SAT), and have it remain NP. So if for one NP hard problem, you find a solution in P, it follows that ALL NP problems are solvable in P.
So basically it boils down to finding a holy grail of algorithms.
P.S. Apologies in advance, I haven't touched my Sipser book in 3 years.
Re:P=PN (Score:2, Informative)
First of all, your example is flawed. The optimization problem of TSP is _not_ polynomial time verifiable. However, if the question is "is there a path on less than k visiting every city", for some k, then the problem is polynomial time verifiable. Also, there are algorithms solving TSP in less than n! time by dynamic programming O(2^n * n^2) or something like that.
But yes, it is mainly the question that "if a solution to the problem P is _verifiable_ in polynomial, can we make an algorithm solving P in polynomial time?".
Re:P=PN (Score:2, Informative)
NP-complete means that a problem is NP-hard and is also known to be in NP. While finding a polynomial time solution to an NP-complete problem would also give a polynomial time solution to everything in NP it is a weaker result, although sufficient to show P=NP.
Re:P=PN (Score:4, Informative)
For NP-complete you need a slight modification of the traveling salesman problem. An example would be that you need to visit 5 cities, but you need to travel less than 50 miles. Is there a route that will get you through all 5 cities in less than 50 miles?
To find a solution need to search through all the permutations (factorial time), but to verify that you have a solution is polynomial time.
However, your original traveling salesman problem is NP-hard because there is no way to verify that you have the shortest route without calculating all of the routes.
I probably have an advantage here because read the Sipser book less than a year ago. Let's see what I remember in another three years. ;)
Re:P=PN (Score:5, Informative)
I think you're using NP, NP Hard, and NP Complete interchangeably, when they are very different.
B is in NP Hard if every A in NP polynomially reduces to B, even if B isn't in NP.
B is in NP Complete if B is NP and also, every A in NP is polynomially reducible to A.
B is in NP if B can be decided in polynomial time by a nondeterministic Turing Machine.
Re:P=PN (Score:4, Informative)
That most programmers do not really need to deal with complexity is really a result of most programmers not working on interesting programs.