Skip to main content.

Courses

Subjects

Course Search

Search Results

Course Prefix: CSE   Course #: 596   Keywords: null   showing 1 to 1 of ~1

CSE 596LEC Introduction to the Theory of Computation

Lecture

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 13, 2020 13:33:43