326008—Decidability- and Complexity Classes
3260DC—Special Topics: Decidability- and
February 18, 2020
1 Time and place:
Thursday 8:30–10:00, BA 9909, beginning March 5.
This course is a follow-up to 326062: Computability Theory. The topics to be covered
- 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.
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.
Oral exam by agreement. Just consult me when you are ready.