326.306Decidability and Complexity Classes Lecturer: Dr. Heinrich Rolletschek Time and place: Thursday, 8:3010: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.
 Polynomialtime complexity.
Literature: Lecture notes will be distributed.
