CISC-462/3.0 Computability and Complexity
Original Author: Kai Salomaa
Last Revised: September 25, 2006
Turing machines and other models of computability such as M-5-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.
Prerequisites: CISC 223/3.0 (or 366/3.0); 365/3.0 is recommended.
The first objective of the course is to provide a thorough introduction
to the theoretical limits of algorithmic computation. We establish that
many naturally occurring and well-defined algorithmic problems are,
even in principle, unsolvable.
In the second part of the course we study the (resource-bounded) complexity
of problems. Here it is important to distinguish the complexity of an
algorithmic problem and the complexity of some particular algorithm
for the problem. The task of determining the complexity of an algorithmic
problem is usually very hard. In particular, the role of nondeterminism
is not well understood and this leads to some of the most important open
problems in theoretical computer science.
- Review of formal languages
Finite automata and regular languages. Context-free grammars.
- Decidability and undecidability
Turing machines. Universality. Diagonalization and the
halting problem. Decidable and undecidable problems for
regular and context-free languages. Recursively enumerable
languages. Extensions of Turing machines. Church-Turing thesis.
Establishing unsolvability using reductions.
- Resource bounded complexity
Time and space bounded computations. Nondeterminism.
Reductions and complete problems for complexity classes.
- Relationships between complexity classes
Savitch's theorem. Time and space hierarchies.
- Selected advanced topics
Rice's theorem. Turing reducibility and relativized computation.
Nondeterministic logarithmic space is closed under complement.
Alternation. Probabilistic algorithms. Interactive proof systems.
- Steven Homer and Alan L. Selman: Computability and Complexity Theory,
Texts in Computer Science, Springer-Verlag, 2001
- Peter Linz: An Introduction to Formal Languages and Automata,
4th ed., Jones and Bartlett Publishers, 2006
- John Martin: Introduction to Languages and the Theory of
Computation, 3rd ed., McGraw Hill, 2003
- Bernard M. Moret: The Theory of Computation, Addison Wesley, 1998
- Michael Sipser: Introduction to the Theory of Computation,
2nd ed., Thomson Course Technology, 2006
- Thomas A. Sudkamp: Languages and Machines - An Introduction to the
Theory of Computer Science, 3rd ed., Pearson Education, Inc.,