Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Course INF-56-53-K-5

Complexity Theory (4V+2U, 8.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 8.0 CP 156 h
4 V Lecture 56 h
2 U Exercise class (in small groups) 28 h
(4V+2U) 8.0 CP 84 h 156 h

Basedata

SWS 4V+2U
CP, Effort 8.0 CP = 240 h
Position of the semester 1 Sem. in WiSe
Level [5] Master (Entry Level)
Language [EN] English
Lecturers
Area of study [INF-ALG] Algorithmics and Deduction
Livecycle-State [NORM] Active

Possible Study achievement

  • Verification of study performance: proof of successful participation in the exercise classes (ungraded)
  • Details of the examination (type, duration, criteria) will be announced at the beginning of the course.

Contents

  • Time Complexity
    • P, NP, NP-completeness.
  • Space Complexity
    • Savitch's theorem, games.
    • NL, Immerman and Szlepcseny's theorem.
  • Diagonalization
    • Hierarchy theorems
    • Ladner's theorem.
  • Parameterized Complexity
    • Graphs of bounded tree width.
    • Courcelle's theorem.
    • Hardness theory.
  • Polynomial Hierarchy
    • Definition and complete problems.
    • Alternation.
    • Collapse
  • Circuits
    • P/poly.
    • Karp and Lipton's theorem.
    • Lower bounds.
    • NC and parallel computing.
  • Randomness
    • BPP.
    • Adleman's theorem.
    • Sipser and Gac's theorem.
  • Countin
      • P.
    • Approximate counting.
    • Toda's theorem.
  • Communication Complexity
    • Fooling sets.
  • Logic in Complexity Theory
    • Alternative definitions of complexity classes.
    • Theories.

Literature

  • Downey, Rodney G., and Michael R. Fellows. Fundamentals of parameterized complexity. Vol. 4. London: Springer, 2013.
  • Hopcroft, John E., Jeffrey D. Ullman, and Rajeev Motwani. Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Vol. 2. Deutschland, München: Pearson Studium, 2002.
  • Papadimitriou, Christos H. Computational complexity. John Wiley and Sons Ltd., 2003.
  • Reischuk, Karl Rüdiger. Einführung in die Komplexitätstheorie. BG Teubner, 1990.
  • Sipser, Michael. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

Further literature will be announced in the lecture.

Requirements for attendance (informal)

None

Requirements for attendance (formal)

None

References to Course [INF-56-53-K-5]

Module Name Context
[INF-56-53-M-5] Complexity Theory P: Obligatory 4V+2U, 8.0 LP
Course-Pool Name
[INF-Alg_V-KPOOL-6] Lectures of the teaching area Algorithmics and Deduction