CISC462/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 M5recursive functions and randomaccess machines. Undecidability. Recursive and recursively enumerable sets. ChurchTuring thesis. Resourcebounded 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.
Objectives
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 welldefined algorithmic problems are,
even in principle, unsolvable.
In the second part of the course we study the (resourcebounded) 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.
Topics
 Review of formal languages

Finite automata and regular languages. Contextfree grammars.
 Decidability and undecidability

Turing machines. Universality. Diagonalization and the
halting problem. Decidable and undecidable problems for
regular and contextfree languages. Recursively enumerable
languages. Extensions of Turing machines. ChurchTuring 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, SpringerVerlag, 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
