Poly-time reductions, where one shows that A ≤P B by showing a poly-time f such that A(x) = B(f(x)).
NP-hard problems: B is NP-hard if A ≤P B for any A in NP.
- B is NP-complete if it is NP-hard and if it is in NP.
- Proving NP-completeness:
Basic idea: if A is NP-hard and A ≤P B, then B is also NP-hard. Consequences:
- Showing that some NP-hard A is in P implies P=NP.
If P≠NP, then every NP-hard A is not in P.
NP-complete problems are the test cases for P=?NP; either they are all in P (and P=NP), or they are all not in P (and P≠NP).
- Cook's Theorem: SAT is NP-complete.
Other reductions: SAT ≤P 3SAT ≤P CLIQUE
Reductions we didn't get to: CLIQUE ≤P INDEPENDENT SET ≤P VERTEX COVER ≤P SUBSET SUM ≤P PARTITION.
See PvsNp and SubsetSumReduction for some of the missing ones and examples of other NP-complete problems. See GareyAndJohnson for many many such problems.