Während traditionelle Komplexitätstheorie zwischen NP-schweren Problemen mit Exponentialzeitalgorithmen und polynomiellen Problemen unterscheidet, hilft die sogenannte feinkörnige Komplexitätstheorie dabei festzustellen, ob ein Problem höchstwahrscheinlich keinen linearen, quadratischen oder auch kubischen Algorithmus haben kann. In diesem Kurs werden wir verschiedene komplexitätstheoretische Vermutungen kennenlernen (SETH, OVH, APSP, 3SUM) und mithilfe von Reduktionen Verbindungen zwischen verschiedenen polynomiellen Problemen herstellen. Ziel ist es, bedingte untere Schranken und dazu passende Algorithmen für polynomielle Probleme zu zeigen.

Bearbeitung regelmäßig erscheinender Übungszettel. Die Bearbeitung kann in Gruppen von bis zu drei Studierenden erfolgen. Insgesamt müssen 50% der Punkte erreicht werden.

Vorlesungsinhalte und Übungszettel werden über Ecampus bereitgestellt: Ecampus-Link

Empfohlen:

• BA-INF 011 – Logik und diskrete Strukturen
• BA-INF 032 – Algorithmen und Berechnungskomplexität I
• BA-INF 041 - Algorithmen und Berechnungskomplexität II