Das P-versus-NP-Problem

Das P-versus-NP-Problem fragt, ob jedes Problem, dessen Lösungen schnell verifiziert werden können, auch schnell gelöst werden kann. Es ist die zentrale offene Frage der theoretischen Informatik und eines der Millennium-Preis-Probleme des Clay Mathematics Institute.

Definition

P ist die Klasse der Probleme, die in Polynomzeit lösbar sind, und NP die Klasse der Probleme, deren vorgeschlagene Lösungen in Polynomzeit verifizierbar sind; das P-versus-NP-Problem fragt, ob diese beiden Klassen gleich sind, was genau dann der Fall ist, wenn ein NP-vollständiges Problem in Polynomzeit lösbar ist.

Scope

Dieses Thema behandelt die formale Aussage von P versus NP, seine Äquivalenz dazu, ob jedes NP-vollständige Problem einen Polynomzeit-Algorithmus besitzt, die Konsequenzen beider Antworten, die Barrieren wie Relativierung, natürliche Beweise und Algebrierung, die den Fortschritt behindert haben, und die weit verbreitete Vermutung, dass sich die Klassen unterscheiden.

Core questions

• Ist das Finden einer Lösung grundsätzlich schwieriger als deren Überprüfung?
• Warum hängt die Antwort davon ab, ob ein einzelnes NP-vollständiges Problem in P liegt?
• Wie würde die Welt aussehen, wenn P gleich NP wäre, und wenn nicht?
• Warum haben jahrzehntelange Bemühungen die Frage nicht lösen können?

Key theories

Äquivalenz zur NP-Vollständigkeit

P ist genau dann gleich NP, wenn jedes NP-vollständige Problem einen Polynomzeit-Algorithmus besitzt, sodass sich die umfassende Frage auf die Lösbarkeit eines einzelnen konkreten Problems wie der Erfüllbarkeit reduziert.

Beweisbarrieren

Relativierungs-, natürliche Beweis- und Algebrierungsresultate zeigen, dass die wichtigsten bekannten Beweistechniken P versus NP nicht klären können, was die Schwierigkeit erklärt und die Suche nach grundlegend neuen Methoden leitet.

Clinical relevance

Die vermutete Ungleichheit von P und NP ist die Arbeitsannahme, die der Behandlung von NP-schweren Problemen als unlösbar zugrunde liegt, sowie der Sicherheit der Kryptographie, da eine effiziente Lösung von NP-Problemen weit verbreitete Verschlüsselungen brechen würde; ein konstruktiver Beweis, dass P gleich NP ist, würde die Optimierung, Logistik und Wissenschaft transformieren.

History

Cook formulierte die Frage 1971 zusammen mit der NP-Vollständigkeit, und sie wurde schnell als fundamental erkannt. Versuche über Schaltungsuntergrenzen in den 1980er Jahren stießen auf die von Razborov und Rudich identifizierte Barriere der natürlichen Beweise, und im Jahr 2000 benannte das Clay Mathematics Institute sie als Millennium-Preis-Problem mit einem Preisgeld von einer Million Dollar.

Debates

Wird P versus NP jemals gelöst werden, und was ist die Antwort?

Die meisten Forscher vermuten, dass P nicht gleich NP ist, aber es existiert kein Beweis, und bekannte Techniken sind nachweislich unzureichend. Die Meinungen gehen auseinander, ob eine Lösung nahe ist, radikal neue Mathematik erfordert oder ob die Frage sogar unabhängig von Standardaxiomen sein könnte.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

Was würde passieren, wenn P gleich NP wäre?

Viele Probleme, die heute als unlösbar gelten, von der optimalen Zeitplanung bis zum Brechen kryptographischer Codes, hätten effiziente Algorithmen, und das Finden von Lösungen wäre nicht schwieriger als deren Überprüfung. Die Auswirkungen auf Handel, Sicherheit und Wissenschaft wären tiefgreifend, weshalb die meisten Experten erwarten, dass P nicht gleich NP ist.

Warum ist das Problem so schwer zu lösen?

Der Beweis, dass P gleich NP ist, erfordert einen schnellen Algorithmus für ein NP-vollständiges Problem, den niemand gefunden hat; der Beweis, dass sie sich unterscheiden, erfordert den Nachweis, dass ein solcher Algorithmus nicht existieren kann. Ergebnisse zur Relativierung und zu natürlichen Beweisen zeigen, dass die Standardtechniken prinzipiell nicht in der Lage sind, Letzteres zu beweisen, sodass ein wirklich neuer Ansatz erforderlich ist.