CS4112 — 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 Godels incompleteness theorem. Time and space complexity, reducibility, completeness for complexity classes, Cook's Theorem, P versus NP, Savitch's Theorem, complexity hierarchy. prereq: no grad cr, 3512 or 3531 or instructor consent, a grade of C- or better is required in all prerequisite courses