Complexity Theory (MSc)

People

Prof. Dr. Jürgen Dix
Dr. rer. nat. Nils Bulling

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

About this course

This lecture is a master course which comes in two version. One is for Clausthal students (1 lecture (2 hours), 1 hour exercise, 1 hour support lecture per week) and the other version is for ITIS students (1 lecture (2 hours), 1 hour exercise per week).
  • 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.

Important issues: first lecture, exercises and exam

  • 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

More detailed 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

Note about slides

  • 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.

Downloads

Complexity-Theory.pdf

Slides

uebung1.pdf

Exercise 1

uebung2.pdf

Exercise 2

uebung3.pdf

Exercise 3

uebung4.pdf

Exercise 4

uebung5.pdf

Exercise 5

uebung6.pdf

Exercise 6

Complexity-Theory.pdf

Slides (2015)

uebung1.pdf

Exercise 1 (2015)

uebung2.pdf

Exercise 2 (2015)

uebung3.pdf

Exercise 3 (2015)

uebung4.pdf

Exercise 4 (2015)

uebung5.pdf

Exercise 5 (2015)

uebung6.pdf

Exercise 6 (2015)

 

Kontakt  Suche  Sitemap  Data Privacy  Imprint
© TU Clausthal 2019