CMPS 132
Turing machines, general phase-structure grammars, the Chomsky hierarchy, recursive functions, diagonalization, the Halting problem, computability and unsolvability, computational complexity, time and space bounds, NP-completeness with emphasis on reductions between problems from various areas. Prerequisite(s): course 130. M. Warmuth, P. Kolaitis, D. Helmbold
(sourced from /cse/classes/cmps132/description.txt)