Search Course Outline

Definitions of computational models and complexity classes: time complexity (e.g., P and NP), space complexity (e.g., L and PSPACE), circuit and parallel complexity (NC), polynomial-time hierarchy (PH), interactive complexity (IP), probabilistic complexity (BPP), and fixed-parameter complexity. Recommended preparation: COMPSCI 320 or 350