Catalog Description: Finite automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.

Units: 4

Related Areas:

• Security (SEC)
• Theory (THY)

Prerequisites: COMPSCI 170

Formats:
Fall: 3.0 hours of lecture and 1.0 hours of discussion per week
Spring: 3.0 hours of lecture and 1.0 hours of discussion per week

Grading Basis: Student Option

Final Exam Status: Yes

---

Class Schedule (Spring 2027):
CS 172 – TuTh 11:00-12:29, Lewis 9 – Alistair J Sinclair

Class Notes
- No time conflicts

- No alternate final

- Class won't be recorded

- Seats reserved for students with enrollment permission are not available upon request. They are reserved for students in internal programs.

Links:

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