Course Detail
Units:
3.0
Course Components:
Lecture
Enrollment Information
Enrollment Requirement:
Prerequisites: CS 3100 AND CS 4150.
Description
Meets with CS 5100. A survey of topics in theoretical computer science, focusing on computability and complexity. Turing machine, decidability, relative computability, recursion theorem, non-deterministic TMs, complexity measures, time and space hierarchies, P and NP, NP-completeness, program specification and verification. Graduate students only. Extra work required.