% 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](http://www.diku.dk/~neil/comp2book2007/book-whole.pdf)]
# Formal Languages and Automata
#. Preliminaries
* [Basic formal language theory](language/)
#. [Finite languages](language/finite/)
#. [Regular languages](language/regular/)
#. [Context-free languages](language/context-free/)
#. *Context-sensitive languages
# Computability
#. [Church-Turing thesis](church-turing/)
* Turing machines
* Turing completeness
* Lambda calculus
* Combinatory logic
* Recursive function
* Cellular automaton
* Abstract rewriting system
#. [Algorithm](algorithm/)
#. [Decidability](decidability/)
* Decidable languages
* Undecidability
* Logical theories
#. [Reducibility](reducibility/)
* Many-one reductions
* Turing reductions, Turing equivalence and Turing degree
#. Recursion theorem
#. Algorithmic information theory
# Complexity
#. [Overview](complexity/)
#. [Time complexity](complexity/time/)
* P and NP
* [NP-completeness](complexity/time/npc/)
#. 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](/algo/approximation/)
* [Probabilistic algorithms](/algo/randomization/)
* BPP
* Alternation
* Interactive proof systems
* IP=PSPACE
* Parallel computation
* NC
* P-completeness
* [Cryptography](/crypto/)