Computer Science 172 — Computability and Complexity (4 Units)

Course Overview

Summary

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.

Prerequisites

• CS 170 (or equivalent)

Topics Covered

• 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
• NP-completeness
• Space-limited computation
• Time and space hierarchy
• Select topics in language theory, complexity, and randomness

Workload

Course Work

• Ten homeworks
• Two midterms
• One final

Time Commitment

There are 3 hours of lecture and 1 hour of discussion per week.

Choosing the Course

When to take

After CS170.

What's next?

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.

Additional Comments/Tips

Last Updated: Summer 2020