CS60069 - Computational Complexity Theory
Brief Syllabus: Elementary space and time complexity classes, inclusion theorems, randomization, circuit complexity classes, counting classes, sublinear space, interactive proof systems.
Computational Complexity, by Christos H. Papadimitriou, Addison-Wesley publishers.
Introduction to the Theory of Computation, by Michael Sipser.
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.