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

Final Exam Status: Written final exam conducted during the scheduled final exam period

---

Class homepage on inst.eecs

Links:

• CS enrollment policies
• EE enrollment policies
• HKN course maps