*****COURSES ARE SUBJECT TO CHANGE*****
Finite automata and regular expressions, universal models of computation, computability and unsolvability, relations between complexity classes, hierarchy theorems, reductions, complete problems for the major complexity classes (L, NL, P, NP, PSPACE). Other topics may include complexity of counting and enumeration problems, complexity of approximation, randomized complexity classes. Prerequisite(s): course 201. D. Helmbold, P. Kolaitis, M. Warmuth
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.