Description
The course presents the main results of computational complexity theory, including complexity classes, reducibilities, and complete sets. Relationships between time and space complexity, between serial and parallel computation, and among deterministic, probabilistic, and nondeterministic computation. Complexity theoretic notions of randomness.
Eric Allender, Joe Kilian, Mario Szegedy
Credits: 3
Category: A
Prerequisites: 16:198:513 and 16:198:509 (or equivalent) are useful.
Semesters Offered:Spring
