Computer Science and EngineeringCSE 204 Computational Models and Complexity

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. (Formerly Computer Science 210.)

Requirements

Prerequisite(s): CSE 201.

Credits

5

Quarter offered

Spring

Instructor

M. Warmuth, P. Kolaitis, D. Helmbold, S. Comandur, A. Van Gelder