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}CLIQUEReductions 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.