Computer Science 172 — Computability and Complexity (4 Units)
This course covers three main areas: automata theory, computability theory, and complexity theory. Automata theory explores what the basic mathematical models of computation are. Computability theory explores what problems can be solved by computers. Complexity theory explores what makes some problems computationally hard and others easy.
- CS 170 (or equivalent)
- Finite Automata and regular languages
- Turing machines
- Polynomial-time equivalence of all reasonable models of computation
- Undecidable, exponential, and polynomial-time problems
- Gödel's Incompleteness Theorems
- Kolmogorov complexity
- Nondeterministic Turing machines
- Space-limited computation
- Time and space hierarchy
- Select topics in language theory, complexity, and randomness
- Ten homeworks
- Two midterms
- One final
There are 3 hours of lecture and 1 hour of discussion per week.
Choosing the Course
When to take
The other 170-series classes (CS174, CS176) might be a good place to look if you like theory-based classes. You may also be interested in CS 278 if you want to learn complexity theory in greater detail.
Usefulness for Research or Internships
Useful if you're interested in pursuing graduate-level complexity theory courses.
Last Updated: Summer 2020