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

Course Schedule