- Course Number: 16:198:538
- Course Type: Graduate
- Semester 1: Spring
- Credits: 3
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.
- Category: A (M.S.), A (Ph.D.)
- Prerequisite Information:
16:198:513 and 16:198:509 (or equivalent) are useful.
- Course Links: 16:198:509 - Foundations of Computer Science, 16:198:513 - Design and Analysis of Data Structures and Algorithms