CMSC 751 - Theory of Computation

[3]

This course is an examination of advanced topics in recursion/computability theory and computational complexity theory. Topics in recursion theory might include: the arithmetic hierarchy, oracles, priority methods, finite injury arguments and infinite injury arguments. Topics in computational complexity theory might include: sparse sets, the Polynomial Hierarchy, probabilistic complexity classes, circuit complexity, Kolmogorov complexity, interactive proofs and derandomization.
Prerequisite: Prerequisite: CMSC 651 or consent of instructor