Complexity Theory (MSc)

People

Prof. Dr. Jürgen Dix
Niklas Fiekas, M.Sc.

Brief course outline

A brief overview about the course is given in the following:

• Chapter 1: The Chomsky Hierarchy.
  In this chapter we shortly review the Chomsky hierarchy to get a common basis and terminology for the later chapters. The slides are quite detailed, but we do not get through all of them. After a short review, we concentrate on the Ehrenfeucht hypothesis and Lindenmayer systems.
• Chapter 2: (Un-)Decidability
  In this chapter, we consider the exact boundary between the decidable and the undecidable. We relate recursive functions and Random Access Machines, present Hilberts problem and introduce one of the strongest tools for showing that a problem is undecidable: the theorem of Rice.
• Chapter 3: Space versus Time: Basics
• Chapter 4: Structure of EXPSPACE

Course description

• Chapter 1: The Chomsky Hierarchy.
  In this chapter we try to get a solid basis for the later chapters. Although we assume knowledge of the Chomsky hierarchy (grammars and machine models), we repeat some topics here, if needed. The detailed slides introduce the precise terminology. In particular we discuss homomorphisms, the minimal finite automaton and closure properties of the languages of the Chomsky hierarchy. We also introduce some topics that normally do not belong to a BSc course on theoretical CS: (1) cf-languages are homomorphic images of the Dyck language, (2) re languages are homomorphic images of cs-languages, (3) equivalence of morphisms on a language L can be reduced to a finite test set (Ehrenfeucht hypothesis), and finally (4) Lindenmayer systems (languages that are orthogonal to the Chomsky hierarchy).
• Chapter 2: (Un-)Decidability
  We first give a detailed illustration of an universal Turing machine in 2.1. (this is just on the slides, will not be covered in the lecture). Then we introduce in Section 2.2 the famous PCP: Post's correspondence problem, introduced by Emil Post in the 40'ies. It can be used to show that many problems are undecidable. In Section 2.3 we consider a problem that looks similar at first sight: sets of word equations over a set of constants and variables. A famous result of Makanin shows that this is a decidable problem. While we are not showing the proof for this result, we show it for a special case (quadratic equations). Section 2.4 introduces the theory of recursive functions: first the Grzegorczyk hierarchy (primitive recursive functions), then the Ackermann function to motivate general (or mu-) partial recursive functions. We relate these hierarchies in Section 2.5 to Random Access machines: Loop programs correspond to levels of the Grzegorczyk hierarchy, while programs correspond to mu-recursive functions. Section 2.6 discusses Hilbert's problem: there is no algorithm to solve diophantine equations over the integers. We also discuss the main steps of the proof of Matiyasevich. Section 2.7 deals with the Theorem of Rice: any nontrivial property of a set of languages is undecidable. We also discuss many applications of this theorem. We introduce a whole hierachy of undecidable languages in Section 2.8: degrees of unsolvability. Section 2.9 introduces several notions of reductions and discusses how they relate to each other.
• Chapter 3: Space versus Time: Basics
• Chapter 4: Structure of EXPSPACE