Theory of Computation and Complexity

Number: 
CMPSC 220
Level: 
Graduate
Units: 
4

Description

Prerequisite: Computer Science 186.
Topics include: models of computation; time and space complexity classes (e.g., P, NP, CO-NP, and Pspace), efficient reducibilities, complete problems lower bounds; the polynomial hierarchy.