Grundlagen der Informatik 2, Vorlesung 21: Komplexitätstheorie - die Klassen P und NP

Der Satz von Rice hat uns hinsichtlich der Entscheidbarkeit mittels algorithmischer Techniken bereits ernüchtert, doch leider ist Entscheidbarkeit nicht die einzige relevante Grenze der Algorithmik. Es ist wenig erquicklich, ein Lösungsverfahren für ein wichtiges Problem zu finden, nur um zu bemerken, dass die Laufzeit des Verfahrens so enorm ist, dass man für relevante Probleminstanzen niemals das Ergebnis zu sehen bekommt. Aus dieser Motivation betrachten wir die Komplexitätsklassen P und NP. Während die Klasse P intuitiv alle Probleme enthält, die man effizient lösen kann, enthält NP intuitiv die Probleme, für die man immerhin nich effizient überprüfen kann, ob eine mögliche Lösung des Problems korrekt ist. Es ist zwar unbekannt ob P=NP ist, bisher gibt es aber kein allgemein bekanntes effizientes Lösungsverfahren für alle NP-Probleme. Wir werden die Technik der Reduktion adaptieren um nachzuweisen, dass Probleme zu den schwierigsten Problemen in NP gehören.