News

The second phase of oral exams will take place in the second week of October. Further details will be published here soon.

The final plan for the exams is online (see the exam section below). Please, pay attention to small modifications compared to the preliminary plan.

We published the results of your homework assignments. 

The preliminary plan for the exams is online (see the exam section below).

The oral exams will take place in on August 8th (see the exam section below).

Topics

Complexity theory is an important addition to the theory of algorithms. Its goal is understanding why certain computational problems are hard and to classify these problems according to their hardness. The important and most famous example is the theory of NP-completeness.

Topics:

  1. Complexity classes, P vs. NP
  2. Reductions and completeness
  3. Space complexity
  4. Hierarchy Theorems
  5. Relativization and oracle turing machines
  6. Polynomial time hierarchy
  7. Probabilistic complexity classes

Module information

  • Module II.2.1: "Modelle und Algorithmen"
  • Lecture L.079.05600
  • "V2 + Ü1 (Kontaktzeit)", i.e. weekly two-hour lectures, one-hour tutorial
  • 4 ECTS-Credits (Workload)
  • Requirements: "Einführung in Berechenbarkeit, Komplexität
    und formale Sprachen" ("Introduction to computability, complexity, and formal languages" or equivalent).

For further information, consider the module handbook.

Dates and times

  • Lecture:
    • Monday, 14:00 - 15:30 (s.t.), Room F1.110
    • (brief discussion of homework solutions afterwards)
  • Tutorial:
    • Monday, 16:00 - 16:45 (s.t.), Room F1.110

Exam and exercise bonus

In order to successfully pass this course, you will have to actively participate by solving homework exercises. More specifically, this means:

  • A necessary requirement for doing the exam is reaching at least 40% of the homework points. This is a formal part of the exam. If you do not reach the 40%, the exam will be graded with 5.0 (failing grade).

Additionally, you can improve your final grade by solving homework exercises:

  • If you reach at least 60% (but less than 80%) of the homework points, your grade improves by 1/3 (one grading step, e.g., from 2.3 to 2.0).
  • If you reach at least 80% of the homework points, your grade improves by 2/3 (two grading steps, e.g., from 2.3 to 1.7).
  • You cannot improve your grade beyond 1.0.
  • Important: An improvement of the grade 5.0 (failing grade) is not possible.

The oral exams will take place in F2.101 on August 8th. Here is the final plan. All questions can be sent to Gennadij Liske (gennadij.liske(at)upb.de).

Lecture

During the semester, we will gradually publish the lecture slides here.

Introduction

Time and space complexity (updated 02.05.16) (book for reference: [2])

Reductions and Complete Problems (updated 02.05.16) (book for reference: [2])

Inside NP (minor update 18.05.16) (book for reference: [3])

Inside P (updated 13.06.16) (book for reference: [2])

Hierarchy Theorems (updated 20.06.16) (book for reference: [2])

Diagonalization

Polynomial Time Hierarchy (updated 04.07.16)

Probabilistic Complexity Classes (updated 11.07.16) (book for reference: [6] in German; [3] in English. Both have a randomness model different from but equivalent to the lecture)

Summary

Tutorials and exercises

Homework

During the semester we will publish exercises allowing you to further deepen your understanding of the lecture's topics at home. We will very likely not publish any sample solutions.

The exercises marked with (*) may prove somewhat more difficult. Do not feel discouraged by this and try to solve these exercises anyway!

You can hand in your solutions at 15:30 directly in the lecture or via Email to your tutor.

We explicitly encourage you to work in small groups (2-3 students) on understanding the lecture and on solving the exercises. This has proven very effective for your success in learning (and your enjoyment of the process). You may also hand in your solutions in such groups.

Homework 1 (due 25.04.)

Homework 2 (due 02.05.)

Homework 3 (due 09.05.)

Homework 4 (due 17.05., hand in via email or via the box at F2.111)

Homework 5 (due 23.05.)

Homework 6 (due 30.05., hand in at the start of the lecture (or via email))

Homework 7 (due 06.06.)

Homework 8 (due 13.06.)

Homework 9 (due 20.06.)

Homework 10 (due 27.06.)

Homework 11 (due 04.07.)

Homework 12 (due 11.07.)

Homework 13 (due 18.07., 14:00. Last sheet.)

Tutorials

Class Handout 1

Class Handout 2

Class Handout 3

Class Handout 4

Class Handout 5 is non-existent (Whit Monday).

Class Handout 6

Class Handout 7 (corrected 30.05.16)

Class Handout 8

Class Handout 9

Class Handout 10

Class Handout 11

Class Handout 12

Class Handout 13

Class Handout 14

 

Homework Results

Literature

Foundations and prior knowledge

  • [1] Michael R. Garey ; David S. Johnson (2005): Computers and intractability. [Nachdr.]. New York: Freeman, ISBN 0-7167-1044-7, 0-7167-1045-5
  • [2] Michael Sipser (2013): Introduction to the theory of computation. 3. ed., Boston, MA.: Cengage Learning, ISBN 1-133-18779-X, 978-1-133-18779-0

Complexity theory

  • [3] Sanjeev Arora ; Boaz Barak (2009): Computational Complexity: A Modern Approach. New York: Cambridge University Press, ISBN 0-521-42426-7
    Draft (with major differences) freely available.
  • [4] Oded Goldreich (2008): Computational complexity. Cambridge [u.a.]: Cambridge Univ. Press, ISBN 978-0-521-88473-0
  • [5] Christos H. Papadimitriou (1994): Computational complexity. Reading, Mass. [u.a.]: Addison Wesley, ISBN 0-02-015308-2, 0-201-53082-1
  • [6] Ingo Wegener (2003): Komplexitätstheorie. Berlin [u.a.]: Springer, ISBN 3-540-00161-1
  • [7] Marcus Schaefer and Christopher Umans (2002): Completeness in the Polynomial-Time Hierarchy: A Compendium. SIGACT News.
    Updated full version freely available.