Models of computation, such as Turing machines and random access machines; nondeterminism and alternation. Computable and noncomputable functions. Time and space complexity, complexity hierarchies, NP-completeness, and provably difficult problems. Proof techniques, such as simulation, diagonalization, and reducibility.

None