Algebra Seminar talk
2022-12-09
Daniel Unterberger
Das P-NP Problem und die Polynomialzeithierarchie
Abstract:
Wir definieren zuerst die Klassen P und NP mithilfe von Turingmaschinen und grundlegenden Begriffen der Komplexitätstheorie. Danach zeigen wir die NP-Vollständigkeit von SAT und definieren aufbauend auf diesen Konzepten die Polynomialzeithierarchie.
Das P-NP-Problem ist ein wichtiges ungelöstes Problem der theoretischen Informatik, das eine Trennung in notwendigem Zeitaufwand für die Berechnung und für das Überprüfen einer Lösung zu beschreiben scheint. coNP und andere Klassen der Polynomialzeithierarchie sind Verallgemeinerungen dieser Konzepte.