P versus NP Problem, in voller polynom versus nichtdeterministische polynom Problem, in computational complexity (ein Teilfeld der theoretischen informatik und mathematik), die Frage, ob alle so genannten NP Probleme sind eigentlich P Probleme. Ein P-Problem ist eines, das in „Polynomzeit“ gelöst werden kann, was bedeutet, dass ein Algorithmus für seine Lösung existiert, so dass die Anzahl der Schritte im Algorithmus durch eine Polynomfunktion von n begrenzt ist, wobei n der Länge der Eingabe für das Problem entspricht., Daher werden P-Probleme als einfach oder nachvollziehbar bezeichnet. Ein Problem wird NP genannt, wenn seine Lösung in Polynomzeit erraten und verifiziert werden kann, und nichtdeterministisch bedeutet, dass keine bestimmte Regel befolgt wird, um die Vermutung zu treffen.

Lineare Programmierprobleme sind selten, da die Anzahl der Schritte in der Simplex-Methode, die 1947 vom amerikanischen Mathematiker George Dantzig erfunden wurde, exponentiell mit der Größe der Eingabe wächst. 1979 entdeckte der russische Mathematiker Leonid Khachian einen Polynomzeitalgorithmus.,, die Anzahl der Rechenschritte wächst als eine Potenz der Anzahl der Variablen, anstatt exponentiell-wodurch gezeigt wird, dass lineare Programmierprobleme tatsächlich P. Diese Entdeckung ermöglichte die Lösung ehemals hartnäckiger Probleme.

Ein Problem ist NP-schwer, wenn ein Algorithmus für seine Lösung geändert werden kann, um ein NP—Problem zu lösen-oder ein P-Problem, da P-Probleme eine Teilmenge von NP-Problemen sind. (Nicht alle NP-Hard-Probleme gehören jedoch zur Klasse der NP-Probleme.) Ein problem, das sowohl in NP und NP-schwer ist sagte zu werden NP-vollständig., Daher impliziert das Finden eines effizienten Algorithmus für jedes NP-vollständige Problem, dass ein effizienter Algorithmus für alle NP-Probleme gefunden werden kann, da eine Lösung für jedes Problem, das zu dieser Klasse gehört, in eine Lösung für jedes andere Mitglied der Klasse umformuliert werden kann., 1971 bewies der amerikanische Informatiker Stephen Cook, dass das Problem der Zufriedenstellbarkeit (ein Problem der Zuweisung von Werten zu Variablen in einer Formel in der Booleschen Algebra, so dass die Aussage wahr ist) NP-vollständig ist, was das erste Problem war, das NP-vollständig war und den Weg ebnete, um andere Probleme zu zeigen, die Mitglieder der Klasse der NP-vollständigen Probleme sind. Ein berühmtes Beispiel für ein NP-vollständiges Problem ist das Problem des reisenden Verkäufers, das breite Anwendungen bei der Optimierung von Transportplänen aufweist., Es ist nicht bekannt, ob jemals Polynomzeitalgorithmen für NP-vollständige Probleme gefunden werden, und festzustellen, ob diese Probleme nachvollziehbar oder hartnäckig sind, bleibt eine der wichtigsten Fragen in der theoretischen Informatik. Eine solche Entdeckung würde beweisen, dass P = NP = NP viele Bereiche der Informatik und Mathematik vervollständigt und revolutioniert.

Beispielsweise beruht die moderne Kryptographie auf der Annahme, dass das Factoring des Produkts zweier großer Primzahlen nicht P ist., Beachten Sie, dass die Überprüfung des Produkts aus zwei Primzahlen einfach ist (Polynomzeit), die Berechnung der beiden Primfaktoren jedoch schwierig ist. Die Entdeckung eines effizienten Algorithmus zum Factoring großer Zahlen würde die meisten modernen Verschlüsselungsschemata brechen.

Im Jahr 2000 entwickelte der amerikanische Mathematiker Stephen Smale eine einflussreiche Liste von 18 wichtigen mathematischen Problemen zur Lösung im 21. Das dritte Problem auf seiner Liste war das P gegen NP Problem., Auch im Jahr 2000 wurde es als Millennium-Problem bezeichnet, eines von sieben mathematischen Problemen, die vom Clay Mathematics Institute in Cambridge, Massachusetts, USA, für einen Sonderpreis ausgewählt wurden. Die Lösung für jedes Millennium-Problem ist $1 Million wert.