326.306-Decidability and Complexity Classes

Lecturer: Dr. Heinrich Rolletschek

Time and place: Thursday, 8:30-10:00, K 123A.

Prerequisites: This course is based on 326.303: Computability Theory.

Contents: The first part of this course deals with classical topics of recursive function theory, thus continuing the material from Computability Theory. Next it deals with the undecidability of problems which do not strictly belong to recursive function theory. Finally, the second half concerns abstract complexity theory. The main topics are:

• Basic theory of reducbility relations.
• The arithmetical hierarchy.
• Post's problem..
• Undecidability of certain word problems.
• Elementary arithmetic.
• Blum's abstract complexity theory.
• Subrecursive hierarchies.
• Complexity theory for computation on Turing machines.
• Polynomial-time complexity.