Skip to main content.



Course Search

Search Results

Course Prefix: CSE   Course #: 596   Keywords:     showing 0 to 1

CSE 596LEC 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.

Credits: 3
Grading: Graded (GRD)
Typically Offered: Varies
Visit the Office of the Registrar’s Class Schedules page for more detailed and updated information.
Published: May 23, 2022 11:45:07