Decidability- and Complexity Classes
Dr. Heinrich Rolletschek
February 13, 2008
Thursday 8:30-10:00, K034D.
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
- C. Papadimitriou: Computational Complexity. Addison-Wesley 1994.
Oral exam by agreement. Just consult me when you are ready.