CS 278. Machine-Based Complexity Theory
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.
Links: