% Theory of Computation % Mort Yao % 2017-04-12
Textbook:
- Michael Sipser. Introduction to the Theory of Computation, 3rd edition.
Supplementary reading:
- Neil Jones. Computability and Complexity: From a Programming Perspective. [PDF]
#. Preliminaries * Basic formal language theory #. Finite languages #. Regular languages #. Context-free languages #. *Context-sensitive languages
#. Church-Turing thesis * Turing machines * Turing completeness * Lambda calculus * Combinatory logic * Recursive function * Cellular automaton * Abstract rewriting system #. Algorithm #. Decidability * Decidable languages * Undecidability * Logical theories #. Reducibility * Many-one reductions * Turing reductions, Turing equivalence and Turing degree #. Recursion theorem #. Algorithmic information theory
#. Overview #. Time complexity * P and NP * NP-completeness #. Space complexity * Savitch's theorem * PSPACE * PSPACE-completeness * L and NL * NL-completeness * NL=coNL #. Provable intractability * Hierarchy theorems * Relativization * Circuit complexity #. Advanced topics * Approximation algorithms * Probabilistic algorithms * BPP * Alternation * Interactive proof systems * IP=PSPACE * Parallel computation * NC * P-completeness * Cryptography