Algorithmically reducing one problem to another as a means of developing algorithms and proving lower bounds. The idea of polynomial time and its independence of many machine models. The classes P and NP and their relationship. Polynomial reducibility and NP-Completeness. A selection of NP-hard problems and proofs of this status.
Approximation algorithms with guarantees of both efficiency and efficacy.
Several examples of these including the traveling salesman problem and bin packing. The idea of intractability as a basis for cryptography. Email a CS Advisor .