Portrait of Ada Lovelace by British painter Margaret Sarah Carpenter (1836)

Alan Turing by Jin Wicked


Complexity Theory • COMPSCI 290.3
Spring 2015

Instructor: Pankaj K. Agarwal

TAs: Abhinandan Nath and Jiangwei Pan

Time: Tue, Thu 3:05-4:20 pm

Location: LSRC D243

Office Hours: Tue, Fri 2:00-3:00pm (D214A LSRC Bldg)

Course Synopsis

This course covers theory of computation and complexity theory. Topics include:

  • Turing machines: Basics, nondeterministic turing machines, tape compression, linear speedup, universal turning machines.
  • Undecidability: Halting problem, recursive and recursively enumerable languages, recursive functions.
  • Complexity classes: Complexity measures, hierarchy theorems, relations among complexity measures, regular languages, reducibilities, complete problems.
  • NP: NP-Completeness, Cook's theorem, other NP-Complete problems, co-NP.
  • Beyond NP: PSPACE, polynomial hierarchy, #P, EXPTIME, EXPSPACE, alternation.
  • Randomized computation: Randomized TM, randomized complexity classes, randomized reductions.
  • Boolean circuits: Size lower bounds, uniform circuits, NC, P-Completeness.
  • Interactive proofs: Interactive proof systems, IP=PSPACE, multiprover interactive proofs, program checking.
  • Cryptography: Perfect secrecy, computational security, one way functions, zero knowledge.
  • Approximability and PCP theorem: Approximation algorithms to NP-hard problems, non-approximability, MAXSNP, PCP, PCP vs. NP.
  • Quantum computation: Quantum superposition and qubits, quantum computation and BQP, search algorithm, factorization.


COMPSCI 230 and 330, or equivalent courses. This course requires undergraduate background in discrete mathematics and algorithms


[AB] S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press.

[Sip] M. Sipser, Introduction to the Theory of Computation, CENGAGE Learning, Boston.

[Pa] C. H. Papadimitriou, Computational Complexity, Addison Welsley.

Reference Books

[G] O. Goldreich, Complexity: A Conceptual Perspective, Cambridge University Press.

[HMU] J. Hopcroft, R. Motwani, J. Ullman, Intriduction to Automata, Languages, and Computation, Addison Welesley.


  • Assignments (four out of five): 30%
  • Midterm exams: 30%
  • Final exam: 40%
  • Both midterm and final will be in-class closed-book exams, and the final exam will be take home.
  • Students are required to use Latex or MS-Word for writing their assignments and to submit the pdf files of their assignments.
  • No credit is given for late solutions.

Collaboration Policy

For assignments, collaboration among students is permitted, but students MUST write up solutions independently on their own and LIST your collaborators for each problem. The assignment questions may be similar to questions on problem sets from past offerings of this course or courses at other universities. Using any preexisting solutions from these or any other sources is strictly prohibited.

page top