Computability and Complexity
Overview
Subject area
CSCI
Catalog Number
722
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
Liberal Arts
Yes
Credits
Minimum Units
3
Maximum Units
3
Academic Progress Units
3
Repeat For Credit
No
Components
Name
Lecture
Hours
3
Requisites
009231