Course Information

CS 721: Introduction to Computational Complexity

A quick overview of computability The Church-Turing thesis, decidability, reducibility, The recursion theorem, self-reference, decidability of logical theories
Time and space complexity Measuring complexity, the classes P, NP, the P versus NP question, NP-completeness, The Cook-Levin Theorem Savitch’s Theorem, separation results, Immerman-Szelepcsenyi Theorem, PSPACE completeness, Logspace computability, the classes L, NL Alternation, alternating complexity classes The polynomial time hierarchy (c) Intractability Hierarchy theorems, exponential space completeness, relativization, circuit complexity (d) Parallel Complexity, Probabilistic Complexity, Interactive Proofs NC and its relation to time-space classes Probabilistic Turing Machines, the class BPP Examples of interactive proof systems, IP=PSPACE (e) Probabilistically Checkable Proofs PCP and the hardness of approximation (f) The Arithmetic Hierarchy, Post’s problem Complete problems in the arithmetic hierarchy, The Friedburg-Muchnik Theorem

M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the theory of NP-completeness, Freeman and Company, 1979.
J. L. Balcazar, J. Diaz and J. Gabarro. Structural Complexity I, EATCS Monographs in Computer Science, Springer, 1988.
J. L. Balcazar, J. Diaz and J. Gabarro. Structural Complexity II, EATCS Monographs in Computer Science, Springer, 1990.
C. Pappadimitriou. Computational Complexity, Addison-Wesley, 1994.
Dexter Kozen. Automata and Computability, Springer, 1997.
Mike Sipser. Introduction to the Theory of Computation, PWS Publishing Company, 1997.
Bernard ME Moret. The Theory of Computation, Addison-Wesley, 1998.
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to AutomataTheory, Languages, and Computation, Second Edition, 2001.
Dexter Kozen. Theory of Computation, Springer, 2006.
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach, Cambridge University Press, March 2009.
Home Page

Not Available

Good undergraduate background in Theory of Computation (CS331) (or Automata and Logic (CS 208)), Design and Analysis of Algorithms (CS 301) (or New design and analysis of Algorithms (CS218)) or equivalent.
Other Details

Duration : Full Semester Total Credit : 6
Type : Theory
Autumn Semester 2019-20

Status : Offered Instructor : Prof. Nutan Limaye
Spring Semester 2019-20

Status : Not Offered Instructor : ---

Last Modified Date: 15-Jul-2013


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback