CISC-462/3.0 Computability and Complexity

Original Author: Kai Salomaa
Last Revised: September 25, 2006

Calendar Description

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. Circuit complexity.

Selected advanced topics
Rice's theorem. Turing reducibility and relativized computation. Nondeterministic logarithmic space is closed under complement. Alternation. Probabilistic algorithms. Interactive proof systems.

Possible Textbooks

  • 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., 2006