UB - University at Buffalo, The State University of New York

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.

http://www.cse.buffalo.edu/courses/cse596

Discrete mathematics and/or courses in mathematics that involve proofs of theorems. Undergraduate course in finite automata theory is recommended.