COIS708
Complexity Theory

Course Description

Models of computation, such as Turing machines and random access machines; nondeterminism and alternation. Computable and noncomputable functions. Time and space complexity, complexity hierarchies, NP-completeness, and provably difficult problems. Proof techniques, such as simulation, diagonalization, and reducibility.


Prerequisite

None


Back to Course List