Computational Complexity

3 credits · Graduate

Turing machines, undecidability, recursive function theory, complexity measures, reduction and completeness, NP, NP-Completeness, co-NP, beyond NP, relativized complexity, circuit complexity, alternation, polynomial time hierarchy, parallel and randomized computation, algebraic methods in complexity theory, communication complexity. Prerequisite: Computer Science 334 or equivalent.