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


Was sind die Unterschiede zwischen? NP, NP-vollständig und NP-Hart?

Ich kenne viele Ressourcen im Internet. Ich würde gerne Ihre Erklärungen lesen, und der Grund ist, dass sie anders sein könnten als das, was da draußen ist, oder es ist da draußen und ich bin mir dessen nicht bewusst.


906
2017-12-07 01:11


Ursprung


Antworten:


Ich nehme an, dass Sie nach intuitiven Definitionen suchen, da die technischen Definitionen einige Zeit zum Verständnis benötigen. Denken wir zunächst an ein vorläufig benötigtes Konzept, um diese Definitionen zu verstehen.

  • Entscheidungsproblem: Ein Problem mit a Ja oder Nein Antworten.

Lasst uns diese nun definieren Komplexitätsklassen.

P

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

Das heißt, bei einem gegebenen Problem kann die Antwort Ja oder Nein in Polynomzeit entschieden werden.

Beispiel

Angesichts einer verbundenen Grafik GKann man seine Ecken mit zwei Farben färben, so dass keine Kante monochromatisch ist?

Algorithmus: Beginne mit einem beliebigen Eckpunkt, färbe ihn rot und alle seine Nachbarn blau und fahre fort. Stoppen Sie, wenn Ihnen die Scheitelpunkte ausgehen oder Sie gezwungen sind, eine Kante zu erstellen, wenn beide Endpunkte die gleiche Farbe haben.


NP

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

Dies bedeutet, dass wenn jemand uns eine Instanz des Problems und ein Zertifikat (manchmal als Zeuge bezeichnet) gibt, dass die Antwort ja ist, wir überprüfen können, ob es in polynomieller Zeit korrekt ist.

Beispiel

Ganzzahlige Faktorisierung ist in NP. Dies ist das Problem, dass ganze Zahlen gegeben sind n und m, gibt es eine ganze Zahl f mit 1 < f < m, so dass f teilt sich n (f ist ein kleiner Faktor von n)

Dies ist ein Entscheidungsproblem, weil die Antworten ja oder nein sind. Wenn uns jemand eine Instanz des Problems gibt (also reichen sie uns ganze Zahlen) n und m) und eine ganze Zahl f mit 1 < f < mund behaupten, dass f ist ein Faktor von n (das Zertifikat), können wir die Antwort überprüfen Polynomzeit durch Ausführen der Teilung n / f.


NP-vollständig

NP-Complete ist eine Komplexitätsklasse, die die Menge aller Probleme darstellt X in NP, für die es möglich ist, jedes andere NP-Problem zu reduzieren Y zu X in Polynomialzeit.

Intuitiv bedeutet dies, dass wir lösen können Y schnell, wenn wir wissen, wie man es löst X schnell. Genau, Y ist reduzierbar auf X, wenn es einen Polynomzeitalgorithmus gibt f um Instanzen zu transformieren y von Y zu Instanzen x = f(y) von X in Polynomialzeit, mit der Eigenschaft, dass die Antwort auf y ist ja, wenn und nur wenn die antwort auf f(y) ist ja.

Beispiel 

3-SAT. Dies ist das Problem, bei dem uns eine Konjunktion (ANDs) von 3-Satz-Disjunktionen (ORs), Aussagen der Form, gegeben wird

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

wo jeder x_vij ist 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 Nachweis 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 einen von ihnen zu lösen, jedes NP-Problem in polynomieller Zeit lösbar ist (ein Problem, um sie alle zu beherrschen).


NP-hart

Intuitiv sind dies die Probleme, die es gibt mindestens so hart wie die NP-vollständigen Probleme. Beachten Sie, dass NP-schwere Probleme auftreten muss nicht in NP sein, und Sie müssen keine Entscheidungsprobleme sein.

Die genaue Definition ist hier ein Problem X ist NP-schwer, wenn ein NP-vollständiges Problem vorliegt Y, so dass Y ist reduzierbar auf X in Polynomialzeit.

Da jedoch jedes NP-vollständige Problem in Polynomialzeit auf ein beliebiges anderes NP-vollständiges Problem reduziert werden kann, können alle NP-vollständigen Probleme auf jedes NP-schwere Problem in polynomieller Zeit reduziert werden. Wenn es dann eine Lösung für ein NP-schweres Problem in Polynomialzeit gibt, gibt es eine Lösung für alle NP-Probleme in Polynomialzeit.

Beispiel

Das Problem anhalten ist ein NP-schweres Problem. Dies ist das Problem, das ein Programm gegeben hat P und Eingabe I, wird es aufhören? Dies ist ein Entscheidungsproblem, aber es ist nicht in NP. Es ist klar, dass jedes NP-vollständige Problem auf dieses reduziert werden kann. Als ein 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. In der Tat, die Ton-Institut bietet eine Million Dollar für eine Lösung des Problems an (Stephen Cooks aufschreiben 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 oder nicht. Es wird weitgehend angenommen, dass sie es nicht tun. Hier ist ein hervorragender neuer Artikel über die neuesten (und die Wichtigkeit) des P = NP-Problems: Der Status des P-NP-Problems.

Das beste Buch zu diesem Thema ist Computer und Unnachgiebigkeit von Garey und Johnson.


1178
2017-12-07 01:46



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: beliebig NP kann auf NP-Complete reduziert werdenund irgendwas NP-Complete kann auf NP-Hard reduziert werden, alle in P (Polynom) Zeit.

Wenn Sie eine schwierigere Klasse von Problemen in P-Zeit lösen können, werden Sie feststellen, wie Sie alle einfacheren Probleme in P-Zeit lösen können (zum Beispiel P = NP, wenn Sie herausfinden, wie man ein NP-Complete-Problem löst) P Zeit).

____________________________________________________________
| Fehlertyp | Überprüfbar in P Zeit | Lösbar in P Zeit | Schwierigkeit erhöhen
___________________________________________________________ | |
| P | Ja | Ja | |
| NP | Ja | Ja oder Nein * | |
| NP-vollständig | Ja | Unbekannt | |
| NP-Hart | Ja oder Nein ** | Unbekannt *** | |
____________________________________________________________ V

Hinweise zu Yes oder No Einträge:

  • * 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 hart.

Ich habe auch gefunden dieses Diagramm ziemlich nützlich, wenn man sieht, wie alle diese Typen miteinander korrespondieren (achten Sie mehr auf die linke Hälfte des Diagramms).


204
2017-10-22 06:08



Dies ist eine sehr informelle Antwort auf die gestellte Frage.

Kann 3233 als das Produkt von zwei anderen Zahlen größer als 1 geschrieben werden? Gibt es eine Möglichkeit, einen Pfad um alle zu gehen? Sieben Brücken von Königsberg ohne zweimal eine Brücke zu nehmen? Dies sind Beispiele für Fragen, die ein gemeinsames Merkmal haben. Es ist vielleicht nicht offensichtlich, wie man die Antwort effizient bestimmt, aber wenn die Antwort "Ja" ist, dann gibt es einen kurzen und schnellen Beweis. Im ersten Fall eine nicht-triviale Faktorisierung von 51; in der zweiten, eine Route zum Gehen der Brücken (passend zu den Zwängen).

EIN Entscheidungsproblem ist eine Sammlung von Fragen mit Ja oder Nein Antworten, die nur in einem Parameter variieren. Sag das Problem COMPOSITE = {"Ist n Komposit ": n ist eine Ganzzahl} oder EULERPATH = {"Ist das Diagramm? G einen Euler-Pfad haben? ": G ist ein endlicher Graph}.

Einige Entscheidungsprobleme eignen sich nun für effiziente, wenn nicht sogar offensichtliche Algorithmen. 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 man die Antwort erhält - aber wenn Sie einige zusätzliche Informationen kennen, ist es offensichtlich, wie Sie beweisen können, dass Sie die richtige Antwort haben. COMPOSITE ist so: Trial Division ist der offensichtliche Algorithmus, und es ist langsam: Um eine 10-stellige Zahl zu faktorisieren, müssen Sie so etwas wie 100.000 mögliche Divisoren versuchen. Aber wenn Ihnen zum Beispiel jemand gesagt hat, dass 61 ein Teiler 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 zu überprüfen. Wie COMPOSITE. Ein wichtiger Punkt ist, dass diese Definition nichts darüber aussagt, wie schwer das Problem ist. Wenn Sie eine richtige und effiziente Möglichkeit haben, ein Entscheidungsproblem zu lösen, müssen Sie nur die Schritte in der Lösung aufschreiben.

Die Algorithmenforschung wird fortgesetzt, und neue intelligente Algorithmen werden ständig erstellt. Ein Problem, das Sie heute möglicherweise nicht effizient lösen können, könnte morgen eine effiziente (wenn nicht sogar offensichtliche) Lösung sein. In der Tat dauerte es Forscher bis 2002 um eine effiziente Lösung für COMPOSITE zu finden! Bei all diesen Fortschritten muss man sich wirklich fragen: Sind kurze Beweise nur eine Illusion? Könnte sein jeden Entscheidungsproblem, das sich für effiziente Beweise eignet, hat eine effiziente Lösung? Niemand weiß.

Der vielleicht größte Beitrag zu diesem Gebiet kam mit der Entdeckung einer besonderen Klasse von NP-Problemen. Durch das Herumspielen mit Schaltungsmodellen für die Berechnung fand Stephen Cook ein Entscheidungsproblem der NP-Sorte, das nachweislich genauso hart oder härter war jeden anderes NP-Problem. Eine effiziente Lösung für die Boolesches Erfüllbarkeitsproblem könnte verwendet werden, um eine effiziente Lösung zu schaffen Irgendwelche anderen Problem in NP. Bald darauf zeigte Richard Karp, dass eine Reihe anderer Entscheidungsprobleme dem gleichen Zweck dienen könnten. Diese Probleme, in gewisser Hinsicht die "schwierigsten" Probleme in NP, wurden bekannt als NP-vollständig Probleme.

Natürlich ist NP nur eine Klasse von Entscheidungsproblemen. Viele Probleme werden auf diese Weise nicht natürlich angegeben: "Finde die Faktoren von N", "Finde den kürzesten Pfad im Graphen G, der jeden Knoten besucht", "gebe einen Satz von Variablenzuweisungen, der den folgenden booleschen Ausdruck wahr macht". Obwohl man informell darüber sprechen kann, dass solche Probleme "in NP" sind, macht das technisch gesehen nicht viel Sinn - sie sind keine Entscheidungsprobleme. Einige dieser Probleme könnten sogar die gleiche Stärke haben wie ein NP-vollständiges Problem: Eine effiziente Lösung für diese (Nicht-Entscheidungs-) Probleme würde direkt zu einer effizienten Lösung für jedes NP-Problem führen. Ein Problem wie dieses wird genannt NP-hart.


70
2017-12-07 02:42



Neben den anderen tollen Antworten, hier ist der typisches Schema Menschen verwenden, um den Unterschied zwischen NP, NP-Complete und NP-Hard zu zeigen:

enter image description here


49
2017-11-24 17:50



Der einfachste Weg, um P v. NP und dergleichen zu erklären, ohne in technische Details zu verfallen, ist der Vergleich von "Wortproblemen" mit "Multiple-Choice-Problemen".

Wenn Sie versuchen, ein "Wortproblem" zu lösen, müssen Sie die Lösung von Grund auf finden. Wenn Sie versuchen, ein "Multiple-Choice-Problem" zu lösen, haben Sie die Wahl: entweder lösen Sie es wie ein "Wort-Problem", oder versuchen Sie, jede der Antworten einzugeben, und passen Sie die passende Antwort an.

Es kommt häufig vor, dass ein "Multiple-Choice-Problem" viel einfacher ist als das entsprechende "Wortproblem": Das Ersetzen der Kandidatenantworten und das Überprüfen, ob sie passen, kann wesentlich weniger Aufwand erfordern, als die richtige Antwort von Grund auf zu finden.

Wenn wir nun dem Aufwand zustimmen würden, der 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.

Die Essenz von P v. NP ist die Frage: "Gibt es einfache Multiple-Choice-Probleme, die als Wortprobleme nicht einfach sind?" Das heißt, gibt es Probleme, für die es einfach ist, die Gültigkeit einer gegebenen Antwort zu überprüfen, aber diese Antwort von Grund auf schwierig zu finden?

Jetzt, wo wir intuitiv verstehen, was NP ist, müssen wir unsere Intuition herausfordern. Es stellt sich heraus, dass es "Multiple-Choice-Probleme" gibt, die in gewissem Sinne am schwersten sind: Wenn man eine Lösung für eines dieser "schwierigsten Probleme" finden würde, wäre man in der Lage, eine Lösung für ALLE zu finden NP Probleme! Als Cook das vor 40 Jahren entdeckte, war es eine völlige Überraschung. Diese "härtesten von allen" -Problemen werden als NP-hart bezeichnet. Wenn Sie eine "Wort-Problem-Lösung" zu einem von ihnen finden, würden Sie automatisch eine "Wort-Problem-Lösung" für jedes "einfache Multiple-Choice-Problem" finden!

Schließlich sind NP-vollständige Probleme diejenigen, die gleichzeitig NP und NP-hart sind. Nach unserer Analogie sind sie gleichzeitig "einfach wie Multiple-Choice-Probleme" und "die schwierigsten von allen als Wortprobleme".


40
2017-08-08 20:41



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

NP (nicht-deterministisch-polynomiale Zeit): Dies sind die Entscheidungsprobleme, die in Polynomialzeit verifiziert werden können. Das heißt, wenn ich behaupte, dass es für ein bestimmtes Problem eine polynomielle Zeitlösung gibt, bitte ich Sie, es zu beweisen. Dann gebe ich Ihnen einen Beweis, den Sie in Polynomialzeit leicht überprüfen können. Diese Art von Problemen werden NP-Probleme genannt. Beachten Sie, dass wir hier nicht darüber sprechen, ob es für dieses Problem eine polynomielle Zeitlösung gibt oder nicht. Aber wir sprechen über die Überprüfung der Lösung eines gegebenen Problems in polynomieller Zeit.

NP-Hard: Diese sind mindestens so hart wie die schwierigsten Probleme in NP. Wenn wir diese Probleme in polynomieller Zeit lösen können, können wir jedes mögliche NP-Problem lösen. Beachten Sie, dass diese Probleme nicht unbedingt NP-Probleme sind. Das heißt, wir dürfen die Lösung dieser Probleme in Polynomialzeit nicht überprüfen.

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 polynomieller Zeit verifiziert werden.


34
2017-10-04 03:50



Ich denke, wir können es viel prägnanter beantworten. Ich antwortete a verwandte Frageund kopiere meine Antwort von dort

Aber zuerst ist ein NP-schweres Problem ein Problem, für das wir nicht beweisen können, dass eine polynomielle Zeitlösung existiert. Die NP-Härte eines "Problem-P" wird gewöhnlich dadurch bewiesen, dass ein bereits bewiesenes NP-schweres Problem in Polynomialzeit in das "Problem-P" umgewandelt wird.

Um den Rest der Frage zu beantworten, müssen Sie zuerst verstehen, welche NP-schweren Probleme auch NP-vollständig sind. Wenn ein NP-hartes Problem zu NP gehört, ist es NP-vollständig. Um zu NP zu gehören, muss ein Problem vorliegen

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

Nun ist es leicht zu sehen, dass es viele NP-schwere Probleme geben könnte, die nicht zu NP gehören und schwerer zu lösen sind. Als ein intuitives Beispiel ist die Optimierungsversion des reisenden Verkäufers, bei der wir einen tatsächlichen Zeitplan finden müssen, schwieriger als die Entscheidungsversion des reisenden Verkäufers, bei der nur festgestellt werden muss, ob ein Zeitplan mit der Länge <= k existiert oder nicht.


16
2018-06-18 16:52



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

Probleme, die in der NP-Komplexitätsklasse liegen, können nicht-deterministisch in Polynomialzeit gelöst werden, und eine mögliche Lösung (d. H. Ein Zertifikat) für ein Problem in NP kann auf Korrektheit in Polynomialzeit verifiziert werden.

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

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

2) verifiziere, dass diese k Knoten eine Clique bilden.

Die obige Strategie ist polynomisch in der Größe des Eingabediagramms und daher ist das k-Cliquenproblem in NP.

Beachten Sie, dass alle Probleme, die in polynomieller Zeit deterministisch lösbar sind, auch in NP sind.

Wenn Sie zeigen, dass ein Problem NP-schwer ist, bedeutet dies normalerweise eine Reduzierung von einem anderen NP-schweren Problem auf Ihr Problem mithilfe einer Polynomzeit-Abbildung: http://en.wikipedia.org/wiki/Reduction_(komplexity)


15
2017-12-07 01:45



Es gibt wirklich nette Antworten für diese spezielle Frage, also hat es keinen Sinn, meine eigene Erklärung zu schreiben. Also werde ich versuchen, mit einer ausgezeichneten Quelle zu verschiedenen Klassen von Rechenkomplexität beizutragen.

Für jemanden, der denkt, dass Rechenkomplexität nur über P und NP ist, Hier ist die umfassendste Ressource über verschiedene Komplexitätsprobleme. Abgesehen von den Problemen, die von OP gestellt wurden, listete es ungefähr 500 verschiedene Klassen von Berechnungsproblemen mit schönen Beschreibungen auf und auch die Liste von grundlegenden Forschungsarbeiten, die die Klasse beschreiben.


5
2018-01-14 01:56



Wie ich es verstehe, ein np-schwer Problem ist nicht "härter" als ein NP-abgeschlossen Problem. In der Tat ist per Definition jedes np-vollständige Problem:

  1. in NP
  2. np-schwer

enter image description here

- Einleitung zu Algorithmen (3ed) von Cormen, Leiserson, Rivest und Stein, pg 1069


2
2017-08-13 13:57