Skip to content Skip to navigation

Complexity Of Computation

16:198:538

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.

Credits: 
3
Category: 
A (M.S.)
A (Ph.D.)
Prerequisite: 

16:198:513 and 16:198:509 (or equivalent) are useful.

Semesters: 
Spring
Teaching Professors Names: 
Eric Allender
Mario Szegedy