Course Detail
Units:
3.0
Course Components:
Lecture
Enrollment Information
Enrollment Requirement:
Prerequisite: CS 3100 and 4100.
Description
Meets with CS 6100. 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. Undergraduate students only.