CS 151
Complexity Theory
12 units (3-0-9)
|
third term
Prerequisites: CS 21 and CS 38, or instructor's permission.
This course describes a diverse array of complexity classes that are used to classify problems according to the computational resources (such as time, space, randomness, or parallelism) required for their solution. The course examines problems whose fundamental nature is exposed by this framework, the known relationships between complexity classes, and the numerous open problems in the area. Not offered 2025-26.
Instructor:
Umans
Published Date:
Aug. 28, 2025