Course Objective:
This is a first course in computational complexity theory designed for graduate and motivated undergraduate students that introduces the basic time and space complexity classes, randomized complexity class and parallel complexity classes. The students also learn about typical problems in these classes. Through the classical results covered, students would learn about the relations between some of these complexity classes.
Course Contents

Review of Basics Concepts. Turing Machine Model of Computation, Universal Turing Machines, Deterministic Turing Machine and Class P. Nondeterministic Turing Machines and Class NP. Satisfiability and Circuit Value Problems. Polynomial time verifiability, Polynomialtime reductions and NPcompleteness. CookLevin Theorem and its proof, Other Time Complexity Classes coNP, EXP and NEXP. (8 lectures)

Diagonalization: Deterministic Time Hierarchy Theorem, Nondeterministic Time Hierarchy Theorem (without proof), Ladner’s Theorem, Oracle Machines and Limits of Diagonalization  BakerGillSolovay theorem. (6 lectures)

Space Complexity: Space Hierarchy Theorem. Classes PSPACE, L, NL and coNL, Savitch’s Theorem, Configuration Graphs, Reachability Problems, Log space reductions, Completeness Results (PSPACE completeness and NLcompleteness), NL=coNL. (6 lectures)

The Polynomial Hierarchy and Circuits: The Polynomial Hierarchy, Alternating Turing Machines, Circuit Model of Computation, Nonuniformity, Class P/poly, KarpLipton Theorem, Parallel Computations and Class NC, Pcompleteness. (8 lectures)

Randomized Computation : Probabilistic Turing Machines, Classes RP, coRP, BPP, ZPP. SipserGacs theorem, Adleman’s theorem. (6 lectures)

Selected advanced topics (either one of the topics from the list below, or any other relevant topic of choice) :
(a) Interactive proofs and the class IP, the class AM, IP=PSPACE, Introduction to PCPs and PCP theorem.
Or (b) Complexity of counting the class#P,# Pcompleteness, Valiant’s theorem. (8 lectures)
Learning Outcomes
Upon successful completion of this course, students are expected to
 Know and state the relationship between various complexity classes studied in the course
 State and explain the classical results in computational complexity theory
Text Books:
 Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 1 edition, 2009, ISBN13: 9780521424264.
 Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 1 edition, 2008, ISBN13: 9780521884730.
References:
 Michiel Siper, Introduction to the theory of computation, Cengage, 3 edition, 2014, ISBN 13: 9788131525296.
 Luca Trevisan, Lecture Notes on Computational Complexity, https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf
 Christos H. Papadimitrou, Computational Complexity, Pearson, 1993, ISBN13: 978 0201530827.
Metadata
Proposing Faculty: Department: Computer Science and Engineering Programme: MCaM Proposing date: Approved date: Proposal type: Offerings:
Past Offerings
 Offered in JanMay, 2022 by Krishnamoorthy Dinesh