Vertiefung Komplexitätstheorie
Dozent:innen: Univ.-Prof. Dr. Ernst Althaus; Dr. rer. nat. Markus BlumenstockKurzname: Vertief. Kompl.
Kurs-Nr.: 08.079.290
Kurstyp: Vorlesung/Übung
Voraussetzungen / Organisatorisches
Grundkenntnisse in Mathematik, Berechenbarkeitstheorie (Turingmaschinen, Entscheidbarkeit, Reduktionen) und Komplexitätstheorie (P und NP, NP-Vollständigkeit, O-Notation) sollten vorhanden sein.Für die Übungsstunde ist Dienstag, 12-14 Uhr angedacht, endgültig entschieden wird der Termin in der ersten Vorlesung.
Am Ende gibt es je nach Teilnehmerzahl eine Klausur oder mündliche Prüfungen.
Empfohlene Literatur
Sanjeev Arora, Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009.Robert I. Soare. Turing Computability - Theory and Applications. Springer, 2016.
Inhalt
In dieser Vorlesung geht es um verschiedene Komplexitätsklassen und ihre Verhältnisse zueinander. Dabei beschäftigen wir uns auch mit unentscheidbaren Problemen.Liste geplanter Themen:
Berechenbarkeitstheorie:
- Isomorphiesatz von Myhill
- Rekursionssatz von Kleene
- Konstruktion einer einfachen Menge nach Post
Komplexitätstheorie:
- Satz von Ladner
- Satz von Savitch
- Satz von Immerman-Szelepcsényi
- AKS-Primzahltest
- Satz von Sipser-Gacs-Lautemann
- PCP Theorem (nur, falls die Vorlesung unerwartet schnell vorankommt)
Termine
| Datum (Wochentag) | Zeit | Ort |
|---|---|---|
| 19.04.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 26.04.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 03.05.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 10.05.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 17.05.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 24.05.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 31.05.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 07.06.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 14.06.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 21.06.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 28.06.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 05.07.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |
| 12.07.2017 (Mittwoch) | 10:00 - 12:00 | 05 136 2413 - Neubau Physik/Mathematik |