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.