CS5230: Computational Complexity
Prerequisites: CS3231 (Automata Theory and Formal Languages).
Mathematical maturity.
Lecturer
Sanjay Jain. Office: COM2 #03-59. Email: sanjay@comp.nus.edu.sg
Mid Term Date: Tue, 13 March, 8:30PM
Lectures: Tue 6:30PM (Tutorials will be held after the lecture)
Office Hours: Tue 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
Polynomial-time and logspace reducibility.
NP-completeness.
NP - P and coNP, Polynomial hierarchy, PSPACE.
Approximation algorithms.
Probabilistic complexity classes.
Interactive proofs.
Course Assessment
End Semester Exam: 70%
Mid Term: 30%
Mid Term Date: Tue, 13 March, 8:30PM
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
Cambride University Press (2008).
Lecture Slides/Notes
(The links will be activated as we progress in the semester)
Tutorials