# Decidability- and Complexity Classes

## Dr. Heinrich Rolletschek

### February 9, 2012

Thursday 8:30-10:00, BA 9912.

This course is a followup of 326062: Computability Theory. The topics to
be covered are:

- Review of basics from computability theory.
- 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, logic and arithmetic.
- Brief introduction to Blum's abstract complexity theory
- Complexity theory for Turing machines.
- Complexity classes and NP-completeness.

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

- G. Tourlakis:
*Computability*. Reston Publishing Company 1984.
- J. Hopcroft, J. Ullman:
*Introduction to Automata Theory, Languages and Computation*.
Addison-Wesley 1979, 2007.
- C. Papadimitriou:
*Computational Complexity*. Addison-Wesley 1994.

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