| Kommentar |
In diesem Seminar befassen wir uns mit der Komplexität von booleschen Funktion in eingeschränkten Berechnungsmodellen, wie Schaltkreisen oder Entscheidungsdiagrammen.
Im Gegensatz zur klassischen Komplexitätstheorie, in der boolesche Funktionen bzw. Entscheidungsprobleme bezüglich ihres Ressourcenverbrauchs auf Turingmaschinen charakterisiert werden und Härtebeweise häufig auf unbewiesenen Annahmen, wie P≠NP, beruhen, können untere Schranken an die Größe von bestimmten Schaltkreisen und Entscheidungsbäumen, die konkrete Funktionen berechnen, ohne komplexitätstheoretische Annahmen bewiesen werden.
Ziel des Seminars ist es, verschiedene Berechnungsmodelle für boolesche Funktionen zu kennenzulernen und sich Techniken zum Beweisen unterer Schranken anzueignen. |
