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:

• Security (SEC)
• Theory (THY)

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

---

Links:

• EECS Course Archives (CalNet authentication required)
• CS enrollment policies
• EE enrollment policies
• HKN course maps