CS 675 - COMPUTABILITY AND COMPLEXITY

College of Engineering

Credit(s): 3

The formal study of computation, including computability and computation with limited resources. Church’s thesis and models of computation. Topics will include Turing machines or other basic models of computation; reductions; computable and computably enumerable sets; Rice’s Theorem; decidability and undecidability; basic complexity theory; NP-completeness and notions of intractability. Additional topics may include primitive recursive functions and Grzegorczyk hierarchy; nondeterminism; the arithmetic hierarchy; formal complexity measures; time and space hierarchy theorems; the polynomial hierarchy and PSPACE; probabilistic complexity classes; circuit complexity.

Prereq: CS 575 or consent of instructor.