wake-up-neo.com

Was sind die Unterschiede zwischen NP, NP-Complete und NP-Hard?

Was sind die Unterschiede zwischen NP, NP-Complete und NP-Hard?

Ich kenne viele Ressourcen im gesamten Web. Ich würde gerne Ihre Erklärungen lesen, und der Grund dafür ist, dass sie sich möglicherweise von den dortigen unterscheiden, oder dass es etwas gibt, von dem ich nichts weiß.

1044
DarthVader

Ich gehe davon aus, dass Sie nach intuitiven Definitionen suchen, da das Verständnis der technischen Definitionen einige Zeit in Anspruch nimmt. Erinnern wir uns zunächst an ein vorläufiges Konzept, das zum Verständnis dieser Definitionen erforderlich ist.

  • Entscheidungsproblem : Ein Problem mit einem ja oder nein antworten.

Definieren wir nun diese Komplexitätsklassen.

P

P ist eine Komplexitätsklasse, die die Menge aller Entscheidungsprobleme darstellt, die in Polynomialzeit gelöst werden können.

Das heißt, bei einem gegebenen Fall des Problems kann die Antwort ja oder nein in Polynomzeit entschieden werden.

Beispiel

Können bei einem verbundenen Graphen G seine Scheitelpunkte mit zwei Farben gefärbt werden, sodass keine Kante einfarbig ist?

Algorithmus: Beginnen Sie mit einem beliebigen Scheitelpunkt, färben Sie ihn rot und alle seine Nachbarn blau und fahren Sie fort. Halten Sie an, wenn Sie keine Eckpunkte mehr haben oder eine Kante erstellen müssen, bei der beide Endpunkte dieselbe Farbe haben.


NP

NP ist eine Komplexitätsklasse, die die Menge aller Entscheidungsprobleme darstellt, für die die Fälle, in denen die Antwort "Ja" lautet, Beweise haben, die in Polynomzeit verifiziert werden können.

Das heißt, wenn uns jemand eine Instanz des Problems und ein Zertifikat (manchmal als Zeuge bezeichnet) mit der Antwort "Ja" gibt, können wir überprüfen, ob es in der Polynomzeit korrekt ist.

Beispiel

Ganzzahlfaktorisierung ist in NP. Dies ist das Problem, dass es bei gegebenen ganzen Zahlen n und m eine ganze Zahl f mit 1 < f < m Gibt, so dass fn ( f ist ein kleiner Faktor von n)?

Dies ist ein Entscheidungsproblem, da die Antworten ja oder nein sind. Wenn uns jemand eine Instanz des Problems gibt (also uns ganze Zahlen n und m) und eine ganze Zahl f mit 1 < f < m Und behauptet, dass f ist ein Faktor von n (das Zertifikat), wir können die Antwort in polynomial time überprüfen, indem wir die Division n / f durchführen.


NP-Complete

NP-Complete ist eine Komplexitätsklasse, die die Menge aller Probleme darstellt X in NP), für die es möglich ist, alle anderen NP Problem Y bis X in Polynomzeit.

Intuitiv bedeutet dies, dass wir Y schnell lösen können, wenn wir X schnell lösen können. Genau, Y ist auf X reduzierbar, wenn es einen polynomiellen Zeitalgorithmus f gibt, um Instanzen y von Y in Instanzen x = f(y) von X in Polynomialzeit mit der Eigenschaft, dass die Antwort auf y Ja lautet, wenn und nur wenn die Antwort auf f(y) Ja lautet.

Beispiel

3-SAT. Dies ist das Problem, bei dem wir eine Verknüpfung (ANDs) von 3-Klausel-Disjunktionen (ORs), Anweisungen der Form, erhalten

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

dabei ist jedes x_vij eine boolesche Variable oder die Negation einer Variablen aus einer endlichen vordefinierten Liste (x_1, x_2, ... x_n).

Es kann gezeigt werden, dass jedes NP Problem kann auf 3-SAT reduziert werden. Der Beweis hierfür ist technisch und erfordert die Verwendung der technischen Definition von NP ( basierend auf nicht deterministischen Turing-Maschinen). Dies ist bekannt als Cooks Theorem.

Was NP-vollständige Probleme wichtig macht, ist, dass, wenn ein deterministischer Polynomzeitalgorithmus gefunden werden kann, um eines von ihnen zu lösen, jedes NP Problem in Polynomzeit lösbar ist (ein Problem, um sie alle zu beherrschen).


NP-schwer

Intuitiv sind dies die Probleme, die mindestens so schwer sind wie die NP-vollständigen Probleme. Beachten Sie, dass NP-harte Probleme müssen nicht in NP sein und müssen keine Entscheidungsprobleme sein.

Die genaue Definition hier ist, dass ein Problem X NP-schwer ist, wenn es ein NP-vollständiges Problem Y gibt, so dass Y auf X in polynomialer Zeit.

Da jedoch jedes NP-vollständige Problem in Polynomzeit auf jedes andere NP-vollständige Problem reduziert werden kann, können alle NP-vollständigen Probleme in Polynomzeit auf jedes NP-harte Problem reduziert werden. Wenn es dann eine Lösung für ein NP-hartes Problem in der Polynomzeit gibt, gibt es eine Lösung für alle NP Probleme in der Polynomzeit.

Beispiel

Das Halteproblem ist ein NP-hartes Problem. Dies ist das Problem, das ein gegebenes Programm P und die Eingabe I zum Stillstand bringt. Dies ist ein Entscheidungsproblem, aber es liegt nicht in NP. Es ist klar, dass jedes NP-vollständige Problem auf dieses reduziert werden kann. Als weiteres Beispiel ist jedes NP-vollständige Problem NP-schwer.

Mein liebstes NP-vollständiges Problem ist das Minesweeper-Problem .


P = NP

Dies ist das bekannteste Problem in der Informatik und eine der wichtigsten offenen Fragen in den mathematischen Wissenschaften. Tatsächlich bietet das Clay Institute eine Million Dollar für eine Lösung des Problems an (Stephen Cooks Beschreibung auf der Clay-Website ist ziemlich gut).

Es ist klar, dass P eine Teilmenge von NP ist. Die offene Frage ist, ob NP) - Probleme deterministische polynomielle Zeitlösungen haben. Es wird weitgehend angenommen, dass dies nicht der Fall ist = NP Problem: Der Status des P versus NP Problem .

Das beste Buch zu diesem Thema ist Computers and Intractability von Garey und Johnson.

1342
jason

Ich habe mich umgesehen und viele lange Erklärungen gesehen. Hier ist ein kleines Diagramm, das nützlich sein kann, um zusammenzufassen:

Beachten Sie, wie sich der Schwierigkeitsgrad von oben nach unten erhöht: Jeder NP kann auf NP-vollständig und jeder NP-vollständig reduziert werden kann auf NP-Hard reduziert werden, alles in P-Zeit (Polynom).

Wenn Sie eine schwierigere Klasse von Problemen in P-Zeit lösen können, bedeutet dies, dass Sie herausgefunden haben, wie Sie alle einfacheren Probleme in P-Zeit lösen können P Zeit).

 ____________________________________________________________ 
 | Problemtyp | In P-Zeit überprüfbar Lösbar in P-Zeit | Zunehmende Schwierigkeit 
 ___________________________________________________________ | | 
 | P | Ja | Ja | | 
 | NP | Ja | Ja oder Nein * | | 
 | NP-Complete | Ja | Unbekannt | | 
 | NP-Hard | Ja oder nein ** | Unbekannt *** | | 
 ____________________________________________________________ V 

Anmerkungen zu Yes oder No Einträgen:

  • * Ein NP -Problem, das auch P ist, ist in P-Zeit lösbar.
  • ** Ein NP-Hard-Problem, das auch NP-Complete ist, ist in P-Zeit überprüfbar.
  • *** NP-Complete-Probleme (die alle eine Teilmenge von NP-hard bilden) könnten sein. Der Rest von NP ist nicht schwer.

Ich fand auch dieses Diagramm sehr nützlich, um zu sehen, wie all diese Typen miteinander korrespondieren (achten Sie mehr auf die linke Hälfte des Diagramms).

240
Johnson Wong

Dies ist eine sehr informelle Antwort auf die gestellte Frage.

Kann 3233 als Produkt von zwei anderen Zahlen größer als 1 geschrieben werden? Gibt es eine Möglichkeit, um alle Sieben Brücken von Königsberg herumzulaufen, ohne zweimal eine Brücke zu nehmen? Dies sind Beispiele für Fragen, die ein gemeinsames Merkmal haben. Es ist möglicherweise nicht klar, wie die Antwort effizient ermittelt werden kann, aber wenn die Antwort "Ja" lautet, gibt es einen kurzen und schnell zu überprüfenden Beweis. Im ersten Fall eine nicht-triviale Faktorisierung von 51; im zweiten eine Route zum Überqueren der Brücken (Anpassung an die Zwänge).

Ein Entscheidungsproblem ist eine Sammlung von Fragen mit Ja- oder Nein-Antworten, die sich nur in einem Parameter unterscheiden. Sagen Sie das Problem COMPOSITE = {"Ist n zusammengesetzt": n ist eine Ganzzahl} oder EULERPATH = {"Hat der Graph G einen Euler-Pfad?": G ist ein endlicher Graph}.

Nun bieten sich einige Entscheidungsprobleme für effiziente, wenn nicht offensichtliche Algorithmen an. Euler entdeckte vor über 250 Jahren einen effizienten Algorithmus für Probleme wie die "Sieben Brücken von Königsberg".

Auf der anderen Seite ist es bei vielen Entscheidungsproblemen nicht offensichtlich, wie die Antwort zu erhalten ist. Wenn Sie jedoch zusätzliche Informationen kennen, ist es offensichtlich, wie Sie beweisen müssen, dass Sie die richtige Antwort haben. COMPOSITE ist wie folgt: Die Testteilung ist der offensichtliche Algorithmus und langsam: Um eine 10-stellige Zahl zu faktorisieren, müssen Sie etwa 100.000 mögliche Teiler ausprobieren. Wenn Ihnen zum Beispiel jemand sagt, dass 61 ein Divisor von 3233 ist, ist eine einfache lange Division ein effizienter Weg, um zu sehen, dass sie korrekt sind.

Die Komplexitätsklasse NP ist die Klasse von Entscheidungsproblemen, bei denen die "Ja" -Antworten kurz sind, um Beweise schnell zu überprüfen. Wie COMPOSITE. Ein wichtiger Punkt ist, dass diese Definition nichts darüber aussagt, wie schwer das Problem ist. Wenn Sie eine korrekte und effiziente Methode zur Lösung eines Entscheidungsproblems haben, ist es ausreichend, die Schritte in der Lösung aufzuschreiben.

Die Algorithmenforschung wird fortgesetzt und ständig werden neue clevere Algorithmen entwickelt. Ein Problem, das Sie heute möglicherweise nicht effizient lösen können, hat möglicherweise morgen eine effiziente (wenn auch nicht offensichtliche) Lösung. Tatsächlich brauchten die Forscher bis 2002 , um eine effiziente Lösung für COMPOSITE zu finden! Bei all diesen Fortschritten muss man sich wirklich fragen: Ist es nur eine Illusion, kurze Beweise zu haben? Vielleicht hat jedes Entscheidungsproblem, das sich für effiziente Beweise eignet, eine effiziente Lösung? Niemand weiß .

Der vielleicht größte Beitrag auf diesem Gebiet war die Entdeckung einer besonderen Klasse von NP Problemen. Durch Herumspielen mit Schaltungsmodellen für die Berechnung fand Stephen Cook ein Entscheidungsproblem der Sorte NP, das nachweislich genauso schwer oder schwerer war als jedes anderen NP. Problem. Eine effiziente Lösung für das Boolesche Erfüllbarkeitsproblem könnte verwendet werden, um eine effiziente Lösung für jedes andere Problem in NP zu erstellen. Kurz darauf zeigte Richard Karp, dass eine Reihe anderer Entscheidungsprobleme dem gleichen Zweck dienen könnten. Diese Probleme, in gewisser Weise die "schwersten" Probleme in NP, wurden als NP-vollständige Probleme bekannt.

Natürlich ist NP nur eine Klasse von Entscheidungsproblemen. Viele Probleme werden auf diese Weise nicht auf natürliche Weise angegeben: "Finden Sie die Faktoren von N", "Finden Sie den kürzesten Pfad in der Grafik G, die jeden Scheitelpunkt aufruft", "Geben Sie eine Reihe von Variablenzuweisungen an, die den folgenden booleschen Ausdruck wahr machen". Obwohl man informell über solche Probleme sprechen kann, die "in NP" sind, ist dies technisch nicht sehr sinnvoll - es sind keine Entscheidungsprobleme. Einige dieser Probleme haben möglicherweise sogar die gleiche Stärke wie ein NP-vollständiges Problem: Eine effiziente Lösung dieser (Nichtentscheidungs-) Probleme würde direkt zu einer effizienten Lösung für jedes NP Problem führen. Ein solches Problem heißt NP-hart .

74
Managu

Zusätzlich zu den anderen guten Antworten ist hier das typisches Schema , mit dem die Leute den Unterschied zwischen NP, NP-Complete und NP-Hard zeigen:

enter image description here

56

P (Polynomial Time): Wie der Name schon sagt, sind dies die Probleme, die in der Polynomial Time gelöst werden können.

NP (Nicht-deterministische-Polynom-Zeit): Dies sind die Entscheidungsprobleme, die in der Polynom-Zeit verifiziert werden können. Das heißt, wenn ich behaupte, dass es eine polynomielle Zeitlösung für ein bestimmtes Problem gibt, fordern Sie mich auf, dies zu beweisen. Dann gebe ich Ihnen einen Beweis, den Sie in der Polynomzeit leicht überprüfen können. Diese Art von Problemen nennt man NP Probleme. Beachten Sie, dass wir hier nicht darüber sprechen, ob es für dieses Problem eine polynomielle Zeitlösung gibt oder nicht. Es geht aber darum, die Lösung eines Problems in polynomialer Zeit zu überprüfen.

NP-Hard: Diese sind mindestens so schwer wie die schwersten Probleme in NP. Wenn wir diese Probleme in polynomialer Zeit lösen können, können wir jedes NP Problem lösen, das möglicherweise existiert. Beachten Sie, dass diese Probleme nicht unbedingt NP Probleme sind. Das heißt, wir können/können die Lösung dieser Probleme in Polynomzeit nicht verifizieren.

NP-Complete: Dies sind die Probleme, die sowohl NP als auch NP-Hard sind. Das heißt, wenn wir diese Probleme lösen können, können wir jedes andere NP Problem lösen, und die Lösungen für diese Probleme können in Polynomzeit verifiziert werden.

55

Der einfachste Weg, P v. NP zu erklären, ohne auf technische Aspekte einzugehen, besteht darin, "Wortprobleme" mit "Multiple-Choice-Problemen" zu vergleichen.

Wenn Sie versuchen, ein "Word-Problem" zu lösen, müssen Sie die Lösung von Grund auf neu finden. Wenn Sie versuchen, ein "Multiple-Choice-Problem" zu lösen, haben Sie die Wahl: Lösen Sie es wie ein "Word-Problem", oder versuchen Sie, jede der Ihnen gegebenen Antworten einzufügen, und wählen Sie die passende Kandidatenantwort aus.

Es kommt häufig vor, dass ein "Multiple-Choice-Problem" viel einfacher ist als das entsprechende "Word-Problem": Das Ersetzen der Kandidatenantworten und das Überprüfen, ob sie passen, erfordern möglicherweise erheblich weniger Aufwand als das Finden der richtigen Antwort von Grund auf.

Wenn wir uns nun auf die Anstrengung einigen würden, die die Polynomzeit "leicht" nimmt, dann würde die Klasse P aus "einfachen Wortproblemen" bestehen, und die Klasse NP würde aus "einfachen Multiple-Choice-Problemen" bestehen.

Das Wesen von P vNPist die Frage: "Gibt es einfache Multiple-Choice-Probleme, die nicht so einfach sind wie Word-Probleme?" Das heißt, gibt es Probleme, bei denen es einfach ist, die Gültigkeit einer bestimmten Antwort zu überprüfen, aber es schwierig ist, diese Antwort von Grund auf neu zu finden?

Jetzt, da wir intuitiv verstehen, was NP ist, müssen wir unsere Intuition herausfordern. Es stellt sich heraus, dass es "Multiple-Choice-Probleme" gibt, die in gewisser Weise am härtesten sind: Wenn man eine Lösung für eines dieser "härtesten" Probleme finden würde, könnte man eine Lösung für ALLE finden NP Probleme! Als Cook dies vor 40 Jahren entdeckte, war es eine völlige Überraschung. Diese "schwersten von allen" Probleme werden als NP-schwer bezeichnet. Wenn Sie eine "Word-Problemlösung" für eine von ihnen finden, finden Sie automatisch eine "Word-Problemlösung" für jedes "einfache Multiple-Choice-Problem"!

Schließlich sind NP-vollständige Probleme diejenigen, die gleichzeitigNP und NP-hart sind. Nach unserer Analogie sind sie gleichzeitig "einfach als Multiple-Choice-Probleme" und "am schwierigsten als Word-Probleme".

44
Michael

Ich denke, wir können das viel prägnanter beantworten. Ich beantwortete eine verwandte Frage und kopierte meine Antwort von dort

Aber zunächst ist ein NP-hartes Problem ein Problem, für das wir keine polynomielle Zeitlösung nachweisen können. Die NP-Härte einiger "Problem-P" wird normalerweise durch Konvertieren eines bereits erprobten NP-harten Problems in das "Problem-P" in Polynomzeit bewiesen.

Um den Rest der Frage zu beantworten, müssen Sie zunächst verstehen, welche NP-harten Probleme auch NP-vollständig sind. Wenn ein NP-hartes Problem zur Menge NP gehört, ist es NP-vollständig. Um zur Menge NP zu gehören, muss ein Problem bestehen

(i) ein Entscheidungsproblem,
(ii) die Anzahl der Lösungen für das Problem sollte endlich sein und jede Lösung sollte eine polynomielle Länge haben, und
(iii) Bei einer Lösung mit Polynomlänge sollten wir sagen können, ob die Antwort auf das Problem ja/nein ist

Nun ist leicht einzusehen, dass es viele NP-schwierige Probleme geben kann, die nicht zur Menge NP gehören und schwerer zu lösen sind. Als ein intuitives Beispiel ist die Optimierungsversion des Handlungsreisenden, bei der wir einen tatsächlichen Zeitplan finden müssen, schwieriger als die Entscheidungsversion des Handlungsreisenden, bei der wir nur feststellen müssen, ob ein Zeitplan mit einer Länge <= k existiert oder nicht.

18
Sushant Sharma

NP-vollständige Probleme sind solche Probleme, die sowohl NP-schwer als auch in der Komplexitätsklasse NP sind. Um zu zeigen, dass ein gegebenes Problem NP-vollständig ist, müssen Sie zeigen, dass das Problem sowohl in NP als auch in NP-schwer vorliegt.

Probleme, die in der Komplexitätsklasse NP liegen, können nicht deterministisch in Polynomzeit gelöst werden, und eine mögliche Lösung (dh ein Zertifikat) für ein Problem in NP kann auf ihre Richtigkeit überprüft werden Polynomzeit.

Ein Beispiel für eine nicht deterministische Lösung des k-Clique-Problems wäre:

1) wähle zufällig k Knoten aus einem Graphen aus

2) stelle sicher, dass diese k Knoten eine Clique bilden.

Die obige Strategie ist in der Größe des Eingabegraphen polynomisch, und daher liegt das k-Clique-Problem in NP.

Es ist zu beachten, dass alle in der Polynomzeit deterministisch lösbaren Probleme auch in NP sind.

Das Zeigen, dass ein Problem NP-schwer ist, beinhaltet normalerweise eine Reduzierung von einem anderen NP-harten Problem auf Ihr Problem mithilfe einer polynomiellen Zeitzuordnung: http://en.wikipedia.org/wiki/Reduction_ (complexity) =

16
awesomo

Es gibt wirklich nette Antworten auf diese spezielle Frage, so dass es keinen Grund gibt, meine eigene Erklärung zu schreiben. Daher werde ich versuchen, mit einer hervorragenden Ressource Beiträge zu verschiedenen Klassen von Rechenkomplexität zu leisten.

Für jemanden, der der Meinung ist, dass es bei der Komplexität von Berechnungen nur um P und NP geht, ist hier die umfassendste Ressource zu verschiedenen Problemen mit der Komplexität von Berechnungen. Abgesehen von den vom OP gestellten Problemen wurden ungefähr 500 verschiedene Klassen von Rechenproblemen mit Nizza-Beschreibungen sowie die Liste der grundlegenden Forschungsarbeiten, die die Klasse beschreiben, aufgelistet.

5
Salvador Dali

So wie ich es verstehe, ist ein np-hard Problem nicht "schwerer" als ein np-complete Problem. Tatsächlich ist per Definition jedes np-vollständige Problem:

  1. in NP
  2. np-hard

enter image description here

- Intro. zu Algorithmen (3ed) von Cormen, Leiserson, Rivest und Stein, S. 1069

3
MrDrews

Hier finden Sie einige interessante Definitionen:

enter image description here

1
sendon1982