Catalog Description: Properties of abstract complexity measures; Determinism vs. nondeterminism; time vs. space; complexity hierarchies; aspects of the P-NP question; relative power of various abstract machines.

Units: 3

Related Areas:

Prerequisites: 170.

Formats:
Spring: 3 hours of lecture per week
Fall: 3 hours of lecture per week

Grading Basis: letter

Final Exam Status: No final exam


Class Schedule (Fall 2025):
CS 278 – TuTh 12:30-13:59, Etcheverry 3113 –

Class Notes
* Time conflicts NOT allowed.

* Lecture will NOT be recorded for playback later but notes will be available for those who miss a class.

Class homepage on inst.eecs

Links: