CSE 531
Computational Complexity I
Credits
4.0
Lead Instructor
Anup Rao
Textbook
None
Course Description
Deterministic and nondeterministic time and space complexity, complexity classes, and complete problems. Time and space hierarchies. Alternation and the polynomial-time hierarchy. Circuit complexity. Probabilistic computation. Exponential complexity lower bounds. Interactive proofs.
Prerequisites
CSE majors only; CSE 322 or equivalent.
CE Major Status
None
Course Objectives
none
ABET Outcomes
No outcomes registered
Course Topics