CSCI 722 - Computability and Complexity
Computability and Complexity
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.
Academic Progress Units
Repeat For Credit