Skip to main content.



Course Search

Notice: Undefined variable: subjects in /htdocs/live/catalog/courses/course-search-results.php on line 34

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
Published: Oct 04, 2021 12:32:11