CS5230: Computational Complexity
Prerequisites: CS4232/CS3231 (Theory of Computation).
Mathematical maturity.
Lecturer
Sanjay Jain. Office: COM2 #03-59. Email: sanjay@comp.nus.edu.sg
Mid Term: Mon 21st March, 8:30PM
(face to face, subject to prevailing safety measures)
Final Exam:
(face to face, subject to prevailing safety measures)
Lectures: Mon 6:30PM (Tutorials will be held right after the lecture)
(face to face, subject to prevailing safety measures)
Office Hours: Mon 5:00PM --- 6:00PM or by appointment
Aims and Objectives:
To study measures of difficulty of problem solving.
To introduce some techniques in theoretical computer science such as
nondeterminism, diagonalization, simulation, padding, reduction,
randomization and interaction.
Syllabus
Complexity Classes
Deterministic and nondeterministic Turing machines.
Tape compression and linear speedup.
Complexity of deterministic simulation of
nondeterministic Turing machines.
Space and time hierarchies.
Savitch's Theorem.
Immerman-Szelepscenyi Theorem
Translation Lemma.
Borodin's gap theorem.
Efficient Algorithms
P, NP, Circuits
Polynomial-time and logspace reducibility.
NP-completeness.
NP - P and coNP, Polynomial hierarchy, PSPACE.
Approximation algorithms.
Probabilistic complexity classes.
Interactive proofs.
AM Games
PCP Theorem
Course Assessment
End Semester Exam: 60%
Mid Term: 30%
Tutorials: 10%
All exams are open book.
Reference Material and Books
-
C. H. Papadimitriou, Computational Complexity, Addison Wesley (1994).
-
Garey and Johnson, Computers and Intractability: A Guide to the Theory of
NP-Completeness, Freeman (1979).
-
Oded Goldreich: Computational Complexity: A Conceptual Perspective
Cambridge University Press (2008).
Lecture Slides/Notes: These will be updated as we progress through
the semester
Tutorials