| Course Code: CS564 Course Name: Computational Complexity Prerequisites: A course in Formal Languages and Automata Theory Preamble/ Objectives: This course is intended to study the nature of computation by defining concretely its notion and its limitations. Syllabus: Turing machines: determinism and non-determinism, time and space hierarchy theorems; Time complexity: P, NP, co-NP, EXP, NEXP, hierarchy theorems, PH; Space complexity: PSPACE, NPSPACE, L, NL, hierarchy theorems; Boolean Circuits: P/poly, NC, AC; Probabilistic complexity: RP, coRP, ZPP, BPP, PP; Interactive Proofs: IP=PSPACE. References: 1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 2. C. H. Papadimitriou, Computational Complexity, Pearson, 1994. 3. Michael Sipser, Introduction to the Theory of Computation, Cengage, 2014. 4. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008. |