Computational Complexity (CS5110)
Lectures
Monday (4:00pm--5:25pm) and Thursday (2:30pm--3:55pm)
Venue
C-LH5
Syllabus
Computational Models:
Turing Machines, Encoding Problems, Universal Turing Machines, Robustness of Turing machines, Decidability, Halting Problem.
Complexity Classes, Reductions and Completeness:
Complexity classes, P, NP, reductions, Cook-Levin Theorem.
Diagonalization:
Diagonalization, Hierarchy theorems, Orcales, Relativization.
Space bounded computation:
Configuration graphs, Savitch's Theorem, PSPACE, NSPACE, L, NL, reductions, completeness, complementation.
Polynomial Hierarchy:
Quantifier alternation, completeness, Alternating Turing Machines, Oracle Machines.
Circuits:
Conditional lower bounds (Karp-Lipton Theorem, etc.), Circuit classes.
Randomized Computation:
BPP, RP, coRP, ZPP, Error reduction, Adelman's Theorem, Randomized reductions, Randomized space computation.
Interactive Proofs:
Definitions, Deterministic verifier, Probablisitic verifier, Public coins vs. Private coins.
Evaluations
There will be 4 to 6 assignments and/or Final exam and/or Viva.
Textbook and References
S. Arora and B. Barak (2000), Computational Complexity: A Modern Approach, Cambridge University Press.
https://theory.cs.princeton.edu/complexity/book.pdf
C. Papadimitriou (1994), Computational Complexity, Addison Wesley Longman.
M. Sipser (2014), Introduction to Theory of Computation, Cengange Learning.
Lectures
Lecture 1:
General Information.
Lecture 2:
Revision - Turing machines.
Lecture 3:
Revision - Turing Machines and Uncomputability.
Lecture 4:
P, NP, definitions, examples.
Lectures 5 -- 10:
P, NP, Nondeterminism, Completeness, Reductions, Cook-Levin Theorem, coNP, EXP, NEXP.