This course supplements the introductory course in the theory of computation,
and expands on topics in Complexity Theory.
Turing machines, simulations and the RAM
Time and space complexity classes
The Hierarchy Theorem
Polynomial-time reductions and Complete Problems
NP and NP-Completeness
Oracles and relativized classes
Introdution to the Theory of Computation by
Computers and Intractability by
Garey and Johnson
Introduction to Automata Theory, Languages and
Hopcroft, Motwani and Ullman
(also earlier version by Hopcroft and Ullman).