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
Prerequisite: 

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

Professor: 
Eric Allender
Mario Szegedy
Semester: 
Spring
Course Type: 
Graduate

Check the University Schedule of Classes to see if this course is open.

Request a Special Permission Number here if the class is full.