CS 582 Theory of Computation: Advanced Topics

Complexity theory: study of resource bounded computation, the complexity classes (P, NP, PSPACE, and PH), NP-completeness, relativized computation, randomized classes.