W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


P-NP-Problem

*** Shopping-Tipp: P-NP-Problem

{{Überarbeiten}} Das '''P-NP-Problem''' (auch '''P≟NP''', '''P versus NP''') ist ein ungelöstes Problem der Mathematik und theoretische Informatik 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ätsklasse Komplexitätsklassen P (Komplexitätsklasse) P und NP (Komplexitätsklasse) NP stehen. Erstmals formuliert wurde das Problem 1971, unabhängig voneinander durch Stephen A. Cook 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.

P contra NP
Die Komplexitätsklasse P enthält alle Probleme, welche von Determinismus (Algorithmus) deterministischen Turingmaschinen in Polynomialzeit 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 Sortierverfahren 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.

Lösung des Problems
Bisher existieren zum exakten Lösen von NP-Vollständigkeit 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#Praktische_Unlösbarkeit 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.

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 (Graphentheorie) 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.

Siehe auch
*Karps 21 NP-vollständige Probleme

Weblinks

- P vs NP Problem (Englisch) Kategorie:Komplexitätstheorie
- P vs NP Page Eine Sammlung von Links zu wissenschaftlichen Papieren zum P-NP-Problem (Englisch) ca:P versus NP en:Complexity classes P and NP fi:P=NP fr:Classes de complexité P et NP he:P=NP it:Classi di complessità P e NP ja:P≠NP予想 ko:P-NP 문제 pt:P versus NP ru:Равен?тво кла??ов P и NP sv:P=NP? th:?ลุ่มความซับซ้อน พี ?ละ เอ็นพี tr:P ile NP arasındaki ilişki zh:P/NP问题

*** Shopping-Tipp: P-NP-Problem




[Der Artikel zu P-NP-Problem stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels P-NP-Problem zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite