Pre-requisites : CS203

Syllabus :
Models of computation: Turing Machine, RAM, -recursive function, grammars Undecidability: Rice's Theorem, Post Correspondence Problem, logical theories Complexity classes: P, NP, coNP, EXP, PSPACE, L, NL, ATIME, BPP, RP, ZPP, IP.

Texts :
1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2004.
2. H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, PHI, 1981.

References :
1. J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1979.
2. S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press,2009.
3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
4. D. C. Kozen, Theory of Computation, Springer, 2006.
5. D. S. Garey, G. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.