Computability Theory:

Turing Machines and Effective Computability, The Church-Turing Thesis and a Definition of Algorithms, Different Models of Turing Machines and their Equivalence.                (5L) 

Universal Machines and Diagonalization, Decidable and Undecidable Problems, Reduction, Mapping Reducibility, Computable Functions, Undecidable Problems about Turing Machines and Rice‘s Theorem, Undecidable Problems about CFLs.       (5L)

Other Formalisms, lambda-Calculus.                     (3L) 

The Recursion Theorem, Decidability of Logical Theories, Turing Reducibility, A Definition of Information and Kolmogorov Complexity.                                    (5L) Beyond Undecidability, Godel‘s Incompleteness Theorem, Proof of the Incompleteness Theorem.         (3L)

Complexity Theory:

Time Complexity: Measuring Complexity, Definitions of the Classes P and NP, NP-completeness, Cook-Levin Theorem, Examples of NP-complete Problems - Vertex Cover, Hamiltonian Path, Subset Sum etc.    (5L) 

Space Complexity: Savitch's Theorem, PSPACE, PSPACEcompleteness-The TQBF Problem, Winning Strategies for Games, Generalised Geography, The Classes L and NL, NL-completeness – Searching in Graphs, NL=co-NL.                                      (6L) Intractability: Hierarchy Theorems, Relativization, Circuit Complexity.                          (3L) 

Advanced Topics: Approximation Algorithms, Probabilistic Algorithms and the class BPP, Alternation, Interactive Proof Systems – Graph Nonisomorphism, IP=PSPACE, Parallel Computation and the Class NC, Pcompleteness, A Brief Introduction to Cryptography – Secret keys, Public-key Systems, One-way Functions, Trapdoor Functions.                  (7L) 

Text Books: 

1. Automata and Computability by Dexter C. Kozen

2. Introduction to the Theory of Computation by Michael Sipser (3rd Edition)

Reference Books: 

1. Computability and Complexity Theory (Texts in Computer Science) by Alan L. Selman and Steven Homer 

2. Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak 3. Computational Complexity: A Conceptual Perspective by Oded Goldreich 

4. Computational Complexity by Christos Papadimitriou 

5. Kolmogorov Complexity and Computational Complexity (Monographs in Theoretical Computer Science. An EATCS Series) by Osamu Watanabe 

6. Theory of Computational Complexity 2e (Wiley Series in Discrete Mathematics and Optimization) by DZ Du 

7. P, NP, and NP-Completeness: The Basics of Computational Complexity by Oded Goldreich 

8. Theory of Computation (Texts in Computer Science) by Dexter C. Kozen