CSE 596: Introduction to the Theory of Computation
This page refers to the Fall 2008 offering of CSE 596 only. The information on this page does not necessarily apply to every offering of CSE 596.
Fall 2008
16109
Introduction to the Theory of Computation
Turing machines, RAMs, decidable and computably enumerable sets, partial computable functions; Church-Turing thesis; undecidable problems, diagonalization, Recursion Theorem, Rice's Theorem, Kleene Normal Form Theorem. Time and space complexity bounds, complexity classes, Savitch's Theorem, NL = coNL. NP-completeness, Cook-Levin Theorem, polynomial hierarchy, complete problems for other complexity classes.
Discrete mathematics and/or courses in mathematics that involve proofs of theorems. Undergraduate course in finite automata theory is recommended.
Ph.D.: This course fulfills one CSE General Program Core Course requirement.
M.S.: This course fulfills one Theory/Algorithms Core Course requirement.
