Modulcode:	infCompl-01a
Englische Bezeichnung:	Computational Complexity
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	unregelmäßig (SS22 WS23/24)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	MSc-Inf-Theo (MSc Inf (21)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21))
Lehrsprache:	Englisch
Voraussetzungen:	Inf-Math-B infBL-01a infAAK-01a

Kurzfassung:

An introduction to computational complexity.

Lernziele:

Students

• classify computational problems according to their complexity,
• explain the relationships between various complexity classes as well as fundamental concepts (such as completeness, reductions, oracles) and
• apply and adapt basic techniques and proof strategies.

Lehrinhalte:

• time complexity: NP, coNP, EXP, NEXP
• diagonalization, especially the time hierarchy theorem and the limits of diagonalization
• space complexity: NL, PSPACE
• randomized computation: RP, coRP, ZPP, BPP
• optional: a deterministic logspace algorithm for undirected reachability

Weitere Voraussetzungen:

Prüfungsleistung:

Depending on the number of students:

• portfolio (in combination with a short presentation as a prerequisite)
• oral exam (with a preceding working phase)
• written exam.

Lehr- und Lernmethoden:

• lecture: presentations by lecturer and discussions/work in small groups
• classroom exercise: discussion of solutions of/approaches to home problems

Verwendbarkeit:

Literatur:

[1] S. Arora, B. Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press, Cambrige, UK.

Verweise:

Kommentar:

Alternative prerequisite: Inf-TGI and Inf-LogInf.