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 2022-23.

Instructor: Umans

Please Note

The online version of the Caltech Catalog is provided as a convenience; however, the printed version is the only authoritative source of information about course offerings, option requirements, graduation requirements, and other important topics.