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."
P vs. NP for dummies
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.
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. ;)
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.