CS5112 — Advanced Theory of Computation
Mathematical theory of computation and complexity. Deterministic and nondeterministic Turing machines, Church-Turing Thesis, recursive and recursively enumerable languages. Lambda calculus. Undecidable problems, Rice's Theorem, undecidability of first-order logic and Gödels incompleteness theorem. Time and space complexity, reducibility, completeness for complexity classes, Cook's Theorem, P versus NP, Savitch's Theorem, complexity hierarchy. pre-req: Grad student, CS 3512 or 3531 or instructor consent