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

  1. Review of Basics Concepts. Turing Machine Model of Computation, Universal Turing Machines, Deterministic Turing Machine and Class P. Non-deterministic Turing Machines and Class NP. Satisfiability and Circuit Value Problems. Polynomial time verifiability, Polynomial-time reductions and NP-completeness. Cook-Levin Theorem and its proof, Other Time Complexity Classes co-NP, EXP and NEXP. (8 lectures)

  2. Diagonalization: Deterministic Time Hierarchy Theorem, Non-deterministic Time Hierarchy Theorem (without proof), Ladner’s Theorem, Oracle Machines and Limits of Diagonalization - Baker-Gill-Solovay theorem. (6 lectures)

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

  4. The Polynomial Hierarchy and Circuits: The Polynomial Hierarchy, Alternating Turing Machines, Circuit Model of Computation, Non-uniformity, Class P/poly, Karp-Lipton Theorem, Parallel Computations and Class NC, P-completeness. (8 lectures)

  5. Randomized Computation : Probabilistic Turing Machines, Classes RP, co-RP, BPP, ZPP. Sipser-Gacs theorem, Adleman’s theorem. (6 lectures)

  6. 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,# P-completeness, Valiant’s theorem. (8 lectures)

Learning Outcomes

Upon successful completion of this course, students are expected to

  1. Know and state the relationship between various complexity classes studied in the course
  2. State and explain the classical results in computational complexity theory

Text Books:

  1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 1 edition, 2009, ISBN-13: 978-0521424264.
  2. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 1 edition, 2008, ISBN-13: 978-0521884730.

References:

  1. Michiel Siper, Introduction to the theory of computation, Cengage, 3 edition, 2014, ISBN- 13: 978-8131525296.
  2. Luca Trevisan, Lecture Notes on Computational Complexity, https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf
  3. Christos H. Papadimitrou, Computational Complexity, Pearson, 1993, ISBN-13: 978- 0201530827.

Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: MCaM Proposing date: Approved date: Proposal type: Offerings:

Past Offerings

  • Offered in Jan-May, 2022 by Krishnamoorthy Dinesh