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
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