Vorlesung Komplexitätstheorie II (SS 2022)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
-
Vorlesungstermine:
- Montag 8:00-10:00 in H-B 6414
-
Übungen:
- Montag 10:00-12:00 in H-B 6414
- Die erste Übung findet am 11.04.2022 statt.
Einige Themen
- Relativierte Komplexitätsklassen
- Monotone Schaltkreise und der Satz von Razborov
- Randomisierte Turingmaschinen
- Interaktive Beweissysteme und der Satz von Shamir
- Primes is in P
Übungsblätter
Lehrbücher
- Sanjeev Arora und Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press 2009
- Christo H. Papadimitriou: Computational complexity. Addison-Wesley 2005
- Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer 2003