P=NP? Oder die Frage danach, wie schwierig Probleme sind

Ganz nach dem Motto: „Ich kenne die Lösung nicht, aber ich bewundere das Problem!“ ist man in der Informatik häufig nicht in der Lage, praktikable Lösungen von Problemen zu präsentieren und versucht daher diese „schwierigen“ Probleme in Komplexitätsklassen zu kategorisieren. Man unterscheidet daher Probleme, die zur Lösung einen Algorithmus mit polynomieller Laufzeit besitzen und Probleme, die zur Lösung vermutlich nur Algorithmen mit exponentieller Laufzeit besitzen.

Als Gedankenmodell hat man außerdem nichtdeterministische Algorithmen eingeführt. Ein nichtdeterministischer Algorithmus könnte beim Backtracking alle Entscheidungsmöglichkeit für eine Entscheidung gleichzeitig wählen und mit allen Varianten gleichzeitig die nächsten Entscheidungsschritte durchführen. Dann wären Backtracking-Algorithmen schnell fertig, da sie bei n Knoten/Kanten nur n Schritte benötigen. Sie testen ja alle Varianten gleichzeitig. Mit normalen Computern ist dies natürlich unmöglich, bei Quantencomputern aber durchaus denkbar. Alle Probleme, zu denen ein deterministischer Algorithmus mit polynomieller Laufzeit bekannt ist, fasst man unter der Klasse P zusammen, alle, zu denen ein nichtdeterministischer, polynomieller Algorithmus bekannt ist, unter NP. Charakteristisch für diese Probleme ist auch, dass eine Entscheidungsvariante in polynomieller Zeit mit einem normalen Computer darauf überprüft werden kann, ob sie eine Lösung des Problems darstellt.

Es ist bisher aber nicht bewiesen, dass es keinen Algorithmus für ein Problem aus NP geben kann, der deterministisch in polynomieller Laufzeit durchführbar ist. Dies wird als das P=NP- Problem bezeichnet und ist eines der ungelösten Rätsel der Informatik. Es wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen.

An einer Antwort auf diese Frage ist man aber sehr interessiert. Man kann zeigen, dass ein Algorithmus, der ein Problem aus NP löst, oft auch andere Probleme aus NP lösen würde, wenn man sie entsprechend umwandelt. Man sagt, dass diese Probleme auf das Ursprungsproblem reduziert werden können. Ist diese Umwandlung in polynomieller Zeit möglich, hat mit einer Lösung für das Ursprungsproblem automatisch auch eine Lösung in Polynomialzeit für das andere Problem gefunden. Solche Umwandlungen sind für viele Probleme bekannt. Es würde also ein einziger effizienter Lösungsalgorithmus reichen und man hätte für alle diese schweren Probleme eine effiziente Lösung.

Das Ursprungsproblem wird NP-schwer genannt, wenn alle Probleme aus NP darauf in Polynomialzeit reduziert werden können. Stammt das Problem selbst noch aus NP (es gibt auch noch schwerere Probleme) dann heißt es NP-vollständig. Schon „Anfang der 1970er Jahre zeigten Stephen A. Cook und Leonid Levin unabhängig voneinander, dass es in NP tatsächlich ein derartiges Problem gibt, auf das alle anderen Probleme in NP in Polynomialzeit reduziert werden können: das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von englisch satisfiability)12. Das Problem SAT ist also ein "schwerstes" Problem in NP (Satz von Cook), da eine polynomielle Lösung von SAT alle anderen Probleme aus NP in polynomieller Zeit lösen würde. Es ist allerdings nicht das [einzige] schwerste Problem, denn Richard M. Karp zeigte, dass es in NP Probleme gibt, auf die SAT reduziert werden kann, die also genauso schwer sind wie SAT“¹³.

Im Unterricht bieten sich mit dem Kolorierungsproblem, dem Finden eines Hamiltonkreises und der Suche nach einer möglichst kleinen dominierenden Menge leicht verständliche NP- vollständige Probleme aus dem Bereich der Graphenalgorithmen an.¹⁴

Ein sehr gut lesbarer Wikipedia-Artikel, der die Komplexitätsklassen P und NP definiert und die Frage nach deren Gleichheit erörtert, finden Sie hier: https://de.wikipedia.org/wiki/P-NP-Problem.

¹³ SAT: Gegeben ist eine aussagenlogische Formel F. Gesucht ist eine Belegung der Variablen von F mit den Werten wahr oder falsch, sodass F zu wahr ausgewertet wird.

¹⁴ Artikel NP-Schwere in Wikipedia, Die freie Enzyklopädie. URL: https://de.wikipedia.org/wiki/NP-Schwere (Stand 03.10.2021), vergleiche auch: https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Hintergrundinformationen: Herunterladen [odt][990 KB]

Weiter zu Approximationsalgorithmen