Im nächsten Semester findet die Vorlesung "Effiziente Algorithmen"
nicht statt. Stattdessen wird die Vorlesung "
Algorithmisches Beweisen" angeboten.
Konkrete Themen der Veranstaltung sind:
* Resolution und Resolutionsstrategien
* Schranken für die Beweislänge und der Bezug zum P/NP-Problem
* Frege-Systeme und Erweiterungen
* Untere Schranken für die Breite und Größe von Resolutionsbeweisen
* Die Methode der effizienten Interpolation
* Automatisierbarkeit von Beweissystemen
* Disjunkte NP-Paare zu Beweissystemen.
Mehr dazu findet ihr auf der Homepage.