Complexity Theory

Worum geht's

Du lernst formale Berechnungsmodelle (insbesondere Turing-Maschinen und Schaltkreise) sowie die wichtigsten Komplexitätsklassen (z. B. L, NL, P, NP, PSPACE, EXP, NEXP, PH). Am Ende kannst du Probleme in Bezug auf Zeit- und Platzkomplexität analysieren, Reduktionen und Vollständigkeitsbeweise anwenden und weiterführende Konzepte wie Alternierung, Randomisierung und interaktive Beweissysteme einordnen.

Was du danach kannst

• Kenntnis von Turing-Maschinen als Modell der Berechnung
• Verständnis von Zeit- und Platzkomplexität
• Vertrautheit mit Schaltkreisen als Berechnungsmodell
• Kenntnis zentraler Komplexitätsklassen (L, NL, P, NP, PSPACE, EXP, NEXP, PH)
• Anwendung von Reduktionen und Nachweis von Vollständigkeit
• Verständnis von Diagonalisierung und Polynomialhierarchie
• Einarbeitung in Alternierung, Boolesche Schaltkreise, Randomisierung und Interaktive Beweissysteme
• Fähigkeit zur Analyse neuer Probleme hinsichtlich ihrer Komplexität

Aus was das Modul besteht

• VorlesungVermittlung der theoretischen Inhalte im Vortrag und durch Präsentation
• ÜbungBearbeitung und Besprechung von Übungsblättern; individuelle Rückmeldung durch Korrektur

Lehrmethode

• Vortrag/Präsentationzur strukturierten Vermittlung der Konzepte
• Übungsblätter mit Besprechungzur Vertiefung, Anwendung und individuellen Rückmeldung