1 Time and place:

Thursday 8:30–10:00, BA 9912, beginning March 10.

2 Contents:

This course is a follow-up to 326062: Computability Theory. The topics to be covered are:

• Review of key notions and results from computability theory.
• Reducibility relations: Post’s problem and the arithmetical hierarchy. This belongs to the area of classical recursive function theory.
• Undecidablity results in the realm of word problems and logic.
• Brief introduction to Blum’s abstract complexity theory.
• Complexity theory for Turing machines.
• Comlexity classes and NP-completeness.

3 Literature:

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

• J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, 2007.
• C. Papadimitriou: Computational Complexity. Addison-Wesley 1994.
• K.R. Reischuk: Einführung in die Komplexitätstheorie. Teubner 1990.
• G. Tourlakis: Computability. Reston Publishing Company 1984.

4 Exam

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