Informatik an der TU Clausthal > Abteilungen > Computational Intelligence > Computational Intelligence > Teaching > Summer 2011 > Complexity Theory (MSc)

Dr. rer. nat. Nils Bulling

- 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

- Lecture: Lecture classes are on Mondays from 13:00-15:00
- Exercise: Exercise classes take place every other Wednesday from 13:00-15:00. Students present their solutions to the exercises.
- Support lecture: Support lecture classes take place every other Wednesday from 13:00-15:00. They deepen the understanding in the topic, proofs and technical details are presented. Material covered during these lectures is relevant for Clausthal students and are obligatory for them.

**Begin:**Monday, 4th of April, 13:00 o'clock, Multimediahörsaal, Tannenhöhe.-
**Registration:**Participants have to register in StudIP! **Exercises:**To be handed in before class.**Permission to exam:**In order to be permitted to the exam, Clausthal students must have fulfilled the following requirement: In average 50% of each exercise sheet has to be solved successfully **and** on all but one exercise sheet at least 25% of the points have to be reached.**Exam:**Oral exam, 6th of October 2011.**Videos:**http://video.tu-clausthal.de/vorlesung/306.html

- 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

- The slides are updated after the lectures. New definitions are added and the proofs are also extended (or new proof sketches are added). Therefore the numbering of the theorems, definitions and lemmas changes. It is not in accordance with the lectures anymore, but it is easy to find out.
- There are different definitions of a Turing machine in the literature (often the head of a machine has to move, or there are many halting states, not just one). In the lectures, I am using sometimes one, sometimes another definition (they are all equivalent). However, after the lectures I am trying to adapt the proofs on the slides to the notion of TM we are using. Therefore there are slight discrepancies between the proofs given during the lecture and the final outcome on the slides.

Slides |

Exercise 1 |

Exercise 2 |

Exercise 3 |

Exercise 4 |

Exercise 5 |

Exercise 6 |

Slides (2015) |

Exercise 1 (2015) |

Exercise 2 (2015) |

Exercise 3 (2015) |

Exercise 4 (2015) |

Exercise 5 (2015) |

Exercise 6 (2015) |