Decidability- and Complexity Classes

Dr. Heinrich Rolletschek

March 20, 2006

Time and place:

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

Contents:

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.

Literature:

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.

Exam

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