CMPS132: Computability and Computational Complexity

*****COURSES ARE SUBJECT TO CHANGE*****

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

5 Credits

YearFallWinterSpringSummer
2016-17
2014-15
2013-14
2012-13
2010-11
2009-10
2007-08
2006-07
2005-06
2004-05
2003-04
2002-03
2001-02
2000-01
1999-00
1998-99

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.