P/NP-Problem
Das P=NP-Problem ist ein offenes Problem der theoretischen Informatik, speziell der Komplexitätstheorie. Es ist die Frage, ob die Klasse NP mit der von deterministischen Turingmaschinen in Polynomialzeit entscheidbaren Problemen (der Klasse P) übereinstimmt.Es ist also lediglich zu zeigen, dass das Finden einer Lösung für ein Problem wesentlich schwieriger ist, als nur zu verifizieren, ob eine gegebene Lösung korrekt ist. Dies ist allerdings bisher noch nicht gelungen. Es gibt jedoch viele Anzeichen dafür, dass tatsächlich gilt: P≠NP.
Aufgabe ist es nun, nicht nur die Algorithmen zu klassifizieren, sondern auch die Lösbarkeit von algorithmischen Problemen zu bestimmen. Die zentrale Fragestellung der Komplexitätstheorie ist derzeit die Äquivalenz der Komplexitätsklassen P und NP. Diese beschränken die Ressource Zeit für deterministische (P) bzw. nichtdeterministische (NP) Maschinen polynomiell in Abhängigkeit der Eingabelänge. Es wird allgemein angenommen, dass P≠NP gilt. Die Annahme wird damit begründet, dass es spezielle algorithmische Probleme gibt, die NP-vollständig sind. Kann man für eines dieser Probleme zeigen, dass es in P liegt, so folgt die Äquivalenz von P und NP. Da einige der Probleme aber schon seit mehreren 1000 Jahren bekannt sind, bisher aber noch niemand einen polynomiellen Algorithmus gefunden hat, geht man von Ungleichheit aus.
Bisher ist eine Separierung der beiden Klassen aber noch nicht gelungen, und P≠NP daher noch nicht bewiesen. Die Schwierigkeit beruht generell darin, für algorithmische Probleme untere Schranken für ihre Komplexität anzugeben. Obere Schranken findet man leicht durch Angabe eines Algorithmus, der die entsprechenden Eigenschaften besitzt. Für untere Schranken ist es jedoch nötig zu beweisen, dass kein Algorithmus mit den gewünschten Eigenschaften existiert. Bisher sind kaum Methoden und Verfahren bekannt, um untere Schranken zu beweisen.
Die Menge aller Sprachen (die Gesamtheit aller Eingaben, die ein Algorithmus akzeptiert), die ein deterministischer Algorithmus (bzw. eine deterministische Turingmaschine) in Polynomialzeit lösen kann, bezeichnet man mit P (siehe polynomieller Algorithmus). NP ist hingegen die Menge aller Sprachen, die ein nicht-deterministischer Algorithmus (bzw. eine nicht-deterministische Turingmaschine) in Polynomialzeit lösen kann (siehe NP-Probleme).
Da der Nicht-Existenzbeweis eines polynomiellen Algorithmus sehr schwierig ist (es gibt bis heute so gut wie keine Methoden derartiges nachzuweisen), beschränkt man sich darauf, Probleme zueinander in Beziehung zu setzen und so abzuleiten, wie schwer diese sind. NP-vollständige Probleme zeichnen sich nun dadurch aus, selbst in der Menge der NP-Probleme zu liegen, andererseits aber die Eigenschaft zu besitzen, dass jedes Entscheidungsproblem in dieser Klasse in Polynomialzeit (mit einer deterministischen Turingmaschine) auf dieses reduziert werden kann.
Durch diese spezielle Definition kann man nun annehmen, dass die NP-vollständigen Probleme in gewisser Hinsicht die schwierigsten Probleme in der Klasse der NP-Probleme überhaupt sind. Allerdings bedarf es zur Rechtfertigung des Begriffs eines Existenzbeweises solcher Probleme, der erstmals von E. Karp im Jahre 1972 geliefert wurde.
Aus der Definition der NP-Vollständigkeit folgt nun, dass entweder alle Probleme in NP auch in P liegen, d.h. in der Klasse aller Probleme liegen, die sich in Polynomialzeit mit einer deterministischen Turingmaschine lösen lassen (die Umkehrung ist trivial, alle Probleme aus P liegen auch in NP), oder aber zumindest für die NP-vollständigen Probleme kein deterministischer Polynomialzeit-Algorithmus existiert. Welcher der beiden Fälle zutrifft, ist bis heute nicht bekannt. Diese häufig mit P=NP? abgekürzt Fragestellung gilt derzeit als die wichtigste Fragestellung der Informatik überhaupt und wird auch in der Mathematik als eine der sieben schwierigsten und wichtigsten Fragestellungen betrachtet.
Siehe auch: NP-Vollständigkeit