Computer Science and EngineeringCSE 104 Computability and Computational Complexity

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. (Formerly CMPS 132.)

Requirements

Prerequisite(s): CSE 103.

Credits

5

Quarter offered

Winter, Spring

Instructor

Delbert Bailey, Manfred Warmuth, Allen Van Gelder, Phokion Kolaitis, David Helmbold