The class P is the set of all yes/no problems which have polynomial time algorithms. The class NP is the set of all problems which have a "proof" for the yes answers which can be checked in polynomial time. Examples of proofs- for the Hamilton Cycle problem, a Hamilton cycle; for Clique, a k-clique.
A problem Q is NP-complete if the existence of a polynomial time algorithm for Q implies the existence of a polynomial time algorithm for all problems in NP. SAT was the first problem shown to be NP-complete.
Other problems can be shown to be NP-complete using a reduction.
Example: Given that Hamilton Cycle is NP-complete, prove Hamilton Path is NP-complete.
Proof: Assume you have a polynomial time algorithm for Hamilton Path. We show that this implies the existence of a polynomial time algorithm for all problems in NP.
Design an algorithm for Hamilton Cycle using Hamilton Path as a subroutine (as done on assignment #1). Demonstrate that if Hamilton Path can be solved in polynomial time p(n), then the time for the routine solving Hamilton Cycle is at most the polynomial q(n).
Since Hamilton Cycle is NP-complete, all problems in NP have a polynomial time reduction to Hamilton Cycle. We get a get a polynomial time algorithm for one of these problems by first reducing it to Hamilton Cycle and then applying this reduction to Hamilton Path. As a result, all problems in NP have a polynomial time reduction to Hamilton Path. This is exactly what we need to conclude that Hamilton Path is NP-complete.
The question "Is P = NP ?" is one of the most important open questions in computer science. You could prove that P=NP by giving a polynomial time algorithm for any problem which is NP-complete. To prove P != NP, You need to show that any algorithm for some NP-complete problem has worst case complexity which is not polynomial in the input size (it is not sufficient to show that a particular algorithm takes more than polynomial time). The significance of proving P=NP is that this would immediately give polynomial time algorithms for hundreds of problems which currently have no known efficient (= polynomial time) algorithms.
Return to
Home page for CSC 320.