CSCI 722 - Computability and Complexity
Overview
Course Title
Computability and Complexity
Department(s)
Description
Models of computation such as Turing machines, random access machines, and circuits. Time complexity classes, including P and NP, space complexity classes, including L and NL, and the interrelationships among them. Mapping reducibility and its specializations, including polynomial-time and log-space reducibility. Establishing a first NP-complete problem, such as circuit satisfiability or Boolean-formula satisfiability. P-complete decision problems; NP-complete decision problems; and related approximation algorithms.
Typically Offered
Fall, Spring
Academic Career
Graduate
Credits
Minimum Units
3
Maximum Units
3
Academic Progress Units
3
Repeat For Credit
No
Components
Name
Lecture
Hours
3
Requisites
009231