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
Schweitzer, Pascal, 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 (informal)

None

Requirements for attendance (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 Computer Science Theory [WP] Compulsory Elective
[INF-88.79-SG] M.Sc. Computer Science Formal Fundamentals [WP] Compulsory Elective
[INF-88.79-SG] M.Sc. Computer Science Specialization 1 [WP] Compulsory Elective
[MAT-88.105-SG] M.Sc. Mathematics 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