..
Suche
Hinweise zum Einsatz der Google Suche
Personensuchezur unisono Personensuche
Veranstaltungssuchezur unisono Veranstaltungssuche
Katalog plus

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