P-NP-Problem

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung.

Das P-NP-Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden kann, das Finden einer solchen Lösung jedoch extrem schwierig ist. Formal ist das die Frage, in welcher Beziehung die beiden Komplexitätsklassen P und NP stehen. Erstmals formuliert wurde das Problem 1971, unabhängig voneinander durch Stephen Cook und Leonid Levin.

Das P-NP-Problem gilt als eines der wichtigsten offenen Probleme der Informatik und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen.

[Bearbeiten] P contra NP

Die Komplexitätsklasse P enthält alle Probleme, welche von deterministischen Turingmaschinen in polynomiell beschränkter Zeit algorithmisch gelöst werden können. Das bedeutet anschaulich, dass diese Probleme von heutigen Computern in akzeptabler Zeit gelöst werden können. Beispielsweise liegt das Sortierproblem in P. Dagegen ist NP die Menge aller von nichtdeterministischen Turingmaschinen in polynomiell beschränkter Zeit lösbaren Probleme. Eine nichtdeterministische Turingmaschine hat zu jedem Zeitpunkt eventuell mehrere Möglichkeiten, ihre Berechnung fortzusetzen, der Rechenweg ist deshalb nicht eindeutig bestimmbar. Es handelt sich dabei um ein theoretisches Modell, das nicht gleichwertig zu heutigen Computern ist. Ein Beispiel ist das Rucksackproblem, bei dem man einen beliebig großen Behälter mit vorgegebenen Gegenständen so füllen soll, dass der Behälter maximal gefüllt ist und der Inhalt so wertvoll wie nur möglich ist.

P ist eine Teilmenge von NP, denn die Probleme aus P lassen sich ebenfalls nichtdeterministisch in Polynomialzeit lösen. Unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist, also ob die beiden Klassen identisch sind.

[Bearbeiten] Lösung des Problems

Bisher existieren zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen. Entsprechende Probleme, die garantiert mindestens exponentielle Laufzeit benötigen, veranschaulichen die praktische Unlösbarkeit von NP-vollständigen Problemen (zum Beispiel Türme von Hanoi). Im Gegensatz zu diesen Problemen ist für NP-vollständige Probleme wegen des offenen P-NP-Problems nicht bewiesen, dass ein optimaler Algorithmus exponentielle Laufzeit benötigt. Würde man für eines dieser Probleme einen auf deterministischen Rechenmaschinen polynomiell zeitbeschränkten Algorithmus finden, so könnte jedes beliebige Problem aus NP durch Polynomialzeitreduktion darauf reduziert und somit in deterministischer Polynomialzeit gelöst werden; in diesem Falle wäre also P = NP. Jedoch ist es bisher nicht gelungen, einen solchen Algorithmus zu entwerfen, weshalb der Großteil der Fachwelt vermutet, dass P≠NP gilt. Dies könnte mathematisch dadurch nachgewiesen werden, dass für ein NP-vollständiges Problem bewiesen wird, dass es keinen deterministischen Polynomialzeitalgorithmus zu dessen Lösung gibt.

[Bearbeiten] Praktische Relevanz

Sehr viele auch praktisch relevante Probleme sind NP-vollständig. Die Lösung des Problems könnte daher von großer Bedeutung sein. Der Beweis von P=NP würde bedeuten, dass für Probleme der bisherigen Klasse NP Algorithmen existieren, die eine Lösung in – wesentlich schnellerer – Polynomialzeit generieren können. Da es jedoch in den vergangenen Jahrhunderten noch nicht gelungen ist, auch nur einen einzigen dieser Algorithmen zu finden, ist es zweifelhaft, dass nach dem Existenzbeweis umgehend ein Polynomialzeit-Algorithmus für diese Probleme gefunden würde. Viele praktische Anwendungen für solche Probleme, wie zum Beispiel das Problem des Handlungsreisenden, das Rucksackproblem oder das Problem der Färbung von Graphen, wären dann theoretisch optimal in kurzer Zeit lösbar, ohne dass jedoch ein praktischer Ansatz für ein solches Verfahren bekannt wäre.

Mit dem Beweis von P≠NP wären NP-Probleme endgültig als schwer lösbar klassifiziert. P≠NP entspricht derzeit der Annahme der meisten Wissenschaftler, und der Beweis wäre weniger folgenschwer als der Beweis von P=NP.