Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-56-53-M-5

Complexity Theory (M, 8.0 LP)

Module Identification

Module Number Module Name CP (Effort)
INF-56-53-M-5 Complexity Theory 8.0 CP (240 h)

Basedata

CP, Effort 8.0 CP = 240 h
Position of the semester 1 Sem. in WiSe
Level [5] Master (Entry Level)
Language [EN] English
Module Manager
Lin, Anthony, Prof. Dr. (PROF | DEPT: INF)
Lecturers
Majumdar, Rupak, Prof. Dr. (PROF | DEPT: INF)
Area of study [INF-ALG] Algorithmics and Deduction
Reference course of study [INF-88.79-SG] M.Sc. Computer Science
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part 		Presence-Time /
Self-Study 		SL SL is
required for exa. 		PL CP Sem.
4V+2U INF-56-53-K-5
Complexity Theory
P 84 h 156 h
U-Schein
ja see comments 8.0 WiSe
  • About [INF-56-53-K-5]: Title: "Complexity Theory"; Presence-Time: 84 h; Self-Study: 156 h
  • About [INF-56-53-K-5]: The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.
    • It is a prerequisite for the examination.

Examination achievement PL1

  • Form of examination: written or oral examination
  • Examination Frequency: each winter semester
  • Examination number: 65653 ("Complexity Theory")
    Type of examination will be announced in the lecture. Duration of the examination: ref. examination regulations.

Evaluation of grades

The grade of the module examination is also the module grade.


Contents

From [INF-56-53-K-5] Complexity Theory:
  • 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.

Competencies / intended learning achievements

Upon successful completion of the module, students will be able to
  • explain concepts and methods of complexity theory,
  • explain the importance of complexity boundaries for real problems,
  • and to classify algorithmic problems in terms of their complexity classes.

Literature

From [INF-56-53-K-5] Complexity Theory:
  • 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 of the module (informal)

None

Requirements for attendance of the module (formal)

None

References to Module / Module Number [INF-56-53-M-5]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science [Core Modules (non specialised)] Computer Science Theory [WP] Compulsory Elective
[INF-88.79-SG] M.Sc. Computer Science [Core Modules (non specialised)] Formal Fundamentals [WP] Compulsory Elective
[INF-88.79-SG] M.Sc. Computer Science [Specialisation] Specialization 1 [WP] Compulsory Elective
[MAT-88.105-SG] M.Sc. Mathematics [Subsidiary Topic] Subsidiary Topic (Minor) [WP] Compulsory Elective
Module-Pool Name
[INF-Alg_Ba_V-MPOOL-4] Specialization Bachelor TA Algorithmics and Deduction
[MV-MBINFO-MPOOL-6] Wahlpflichtmodule Maschinenbau mit angewandter Informatik