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