CS 21
Decidability and Tractability
9 units (3-0-6) |
second term
Prerequisites: CS 2 (may be taken concurrently).
This course introduces the formal foundations of computer science, the fundamental limits of computation, and the limits of efficient computation. Topics will include automata and Turing machines, decidability and undecidability, reductions between computational problems, and the theory of NP-completeness.
Instructor:
Umans
Please Note
The online version of the Caltech Catalog is provided as a convenience; however, the printed version is the only authoritative source of information about course offerings, option requirements, graduation requirements, and other important topics.