# Decidability- and Complexity Classes

## Dr. Heinrich Rolletschek

### March 20, 2006

Thursday 12:50-14:20, seminar room Schloß Hagenberg. Further changes are still
possible.

This course is based on 326303: Computability Theory. The topics to be covered are:

- Reducibility relations: Post's problem and the arithmetical hierarchy. This belongs to the area of
classical recursion theory.
- Undecidablity results in the realm of word problems and the theory of elementary arithmetic.
- Abstract complexity theory: Blum's complexity theory, subrecursive hierarchies, and complexity theory
for Turing machines.
- Basic theory of NP-completeness.

Lectures notes will be handed out. The following textbooks also contain chapters relevant
for the course:

- W. Brainerd, L. Landweber:
*Theory of Computation*. Wiley 1974.
- G. Tourlakis:
*Computability*. Reston Publishing Company 1984.
- J. Hopcroft, J. Ullman:
*Introduction to Automata Theory, Languages and Computation*. Addison-Wesley
1979.

Oral exam by agreement. Just consult me when you are ready.