CSE 431
Introduction to Theory of Computation
Credits
3.0
Lead Instructor
Anup Rao
Textbook
- Computational Complexity, Arora
Course Description
Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions.
Prerequisites
either CSE 312 or CSE 322.
CE Major Status
Selected Elective
Course Objectives
Develop the concepts and skills necessary to be able to evaluate the computability and complexity
of practical computational problems.
ABET Outcomes
No outcomes registered
Course Topics
- Turing machines (deterministic, nondeterministic, multitape)
- Church-Turing Thesis
- Decidability and undecidability, diagonalization, and reducibility
- Halting problem, Post correspondence problem, Rice's Theorem, and other undecidability results
- Time and space complexity
- P vs. NP, NP-completeness, Cook's Theorem, and other NP-complete problems
- PSPACE, PSPACE-completeness, PSPACE-complete problems
- L vs. NL, NL-completeness, Savitch's Theorem, Immerman-Szelepcsenyi Theorem