Decidability- and Complexity Classes

Dr. Heinrich Rolletschek

February 9, 2012

Time and place:

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

Contents:

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.

Literature:

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.

Exam

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