Gourt Home::Gourt :: P/NP-Problem
Das P/NP-Problem ist ein ungelöstes Problem der theoretischen Informatik, speziell der Komplexitätstheorie, und wurde vom Clay Mathematics Institute in die Liste der Millennium-Probleme aufgenommen. Es enthält die Beziehung zwischen den Komplexitätsklassen P und NP. 1971 stellten Stephen Cook und Leonid Levin unabhängig voneinander erstmals die Frage, ob diese beiden Komplexitätsklassen identisch sind.
P und NP
Die Komplexitätsklasse P enthält alle Probleme, welche von deterministischen Turingmaschinen in polynomiell beschränkter Zeit gelöst werden können. Dagegen enthält NP die Menge aller von nichtdeterministischen Turingmaschinen in Polynomialzeit lösbaren Probleme. Aus diesen beiden Definitionen geht hervor, dass P eine Teilmenge von NP ist, unklar ist aber, ob NP ebenfalls eine Teilmenge von P ist, also ob die beiden Klassen identisch sind.
Lösung des Problems
Bisher existieren zum exakten Lösen von NP-vollständigen Problemen nur Exponentialzeitalgorithmen auf deterministischen Rechenmaschinen. Würde für eines dieser Probleme ein auf deterministischen Rechenmaschinen polynomiell zeitbeschränkter Algorithmus gefunden, 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 PNP gilt. Dies könnte mathematisch dadurch nachgewiesen werden, dass für ein Problem in NP bewiesen wird, dass es keinen deterministischen Polynomialzeitalgorithmus zu dessen Lösung gibt.
Praktische Relevanz
Die Lösung des Problems ist von großer praktischer Bedeutung. Falls es gelänge, die Identität der Klassen P und NP zu beweisen, würde daraus folgen, dass für Probleme der bisherigen Klasse NP (z. B. das Problem des Handlungsreisenden) Algorithmen existieren, die eine Lösung in – wesentlich schnellerer – polynomialer Zeit generieren können.
Weblinks
P versus NP | Complexity classes P and NP | P=NP | Classes de complexité P et NP | P=NP | Classi di complessità P e NP | P≠NP予想 | P-NP 문제 | Равенство классов P и NP | กลุ่มความซับซ้อน พี และ เอ็นพี | P ile NP arasındaki ilişki | P/NP问题
"P/NP-Problem"