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.

CILO-1: Identify the fundamental open questions in computational complexity and their significance. CILO-2: Analyse relationships between complexity classes. CILO-3: Apply various combinatorial, algebraic and logical techniques for proving complexity lower bounds. CILO-4: Describe why complexity lower bounds are hard to prove, informally and through the formulation of formal mathematical barriers. CILO-5: Analyse relationships between algorithms and lower bounds, in the context of hardness-randomness trade-offs and the algorithmic method.