CSE431: Introduction to Theory of Computation

3

Models of computation, computable and noncomputable functions, space and time complexity, tractable and intractable functions.

CSE 322.

Michael Sisper, Introduction to the Theory of Computation, 2nd edition, International Thompson Publishing, 2006.

Develop the concepts and skills necessary to be able to evaluate the computability and complexity of practical computational problems.

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

Three 50-minute lectures per week. Weekly written assignments. Midterm and final exam.

beame