CMPS 132: Computability and Computational Complexity

• Winter 2008
• Winter 2007
• Winter 2006
• Winter 2005
• Winter 2004
• Winter 2003
• Winter 2002
• Winter 2001
• Winter 2000
• Winter 1999

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, A. Van Gelder, P. Kolaitis, D. Helmbold

5 Credits

Back To Class Listing

While the information on this web site is usually the most up to date, in the event of a discrepancy, please contact your adviser to confirm which information is correct.