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

https://stackoverflow.com/questions/1857244

13-09-2019
|

Frage

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

Ich kenne viele Ressourcen im gesamten Web. Ich mag Ihre Erklärungen lesen, und der Grund ist, dass sie anders sein könnte, was da draußen, oder gibt es etwas, das ich bin mir nicht bewusst.

Lösung

Ich gehe davon aus, dass Sie für eine intuitive Definitionen suchen, da die technischen Definitionen durchaus einige Zeit zu verstehen, erfordern. Zunächst einmal wollen wir ein vorläufiges Konzept benötigte erinnern diese Definitionen zu verstehen.

Entscheidung Problem : Ein Problem mit einer Ja oder Nein Antwort

Lassen Sie uns nun jene 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, eine Instanz des Problems gegeben, lautet die Antwort ja oder nein in Polynomialzeit entschieden werden.

Beispiel:

einen zusammenhängenden Graphen G Da kann seine Ecken mit zwei Farben gefärbt werden, so dass keine Kante monochromatisch ist?

Algorithmus: Beginnen Sie mit einem beliebigen Scheitelpunkt, Farbe es rot und alle seine Nachbarn blau und fortzusetzen. Stoppen Sie, wenn Sie aus Ecken laufen oder Sie sind gezwungen, einen Vorteil zu machen haben beide Endpunkte die gleiche Farbe sein.

NP

NP ist eine Komplexitätsklasse, die die Menge aller Entscheidungsprobleme darstellt, für die die Fälle, in denen die Antwort „Ja“ haben Beweise, die in polynomieller Zeit überprüft werden können.

Das bedeutet, dass, wenn jemand uns eine Instanz des Problems und ein Zertifikats gibt die Antwort (manchmal einen Zeugen genannt) ja zu sein, können wir überprüfen, ob es in polynomialer Zeit korrekt ist.

Beispiel:

Integer-Faktorisierung ist in NP. Dies ist das Problem, die gegebenen ganze Zahlen n und m, gibt es eine ganze Zahl mit f 1 < f < m, so dass f teilt n (f ist ein kleiner Faktor n)?

Dies ist ein Entscheidungsproblem, weil die Antworten ja oder nein sind. Wenn jemand uns eine Instanz des Problems Hände (so sie Hand ganze Zahlen uns n und m) und eine ganze Zahl f mit 1 < f < m, und behaupten, dass f ist ein Faktor von n (das Zertifikat), können wir die Antwort überprüfen in Polynom Zeit durch die Teilung n / f durchgeführt wird.

NP-Complete

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

Intuitiv bedeutet dies, dass wir Y schnell lösen können, wenn wir wissen, wie X schnell zu lösen. Gerade ist Y X reduzierbar, wenn es eine Polynomialzeitalgorithmus f ist Instanzen y von Y Instanzen x = f(y) von X in Polynomialzeit, mit der Eigenschaft, dass die Antwort auf y ist ja, wenn und nur zu transformieren, wenn die Antwort auf f(y) ja ist.

Beispiel:

3-SAT. Das ist das Problem bei dem wir eine Verbindung (ANDs) 3-Klausel Disjunktionen (RUP), Aussagen der Form gegeben werden

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

wobei jedes x_vij ist eine Boolesche Variable oder die Negation einer Variablen aus einer endlichen Liste vordefinierter (x_1, x_2, ... x_n).

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

Was macht NP-vollständige Probleme wichtig ist, dass wenn ein deterministischer Polynomialzeitalgorithmus einer von ihnen gefunden werden kann zu lösen, jedes NP-Problem in Polynomialzeit lösbar ist (ein Problem, sie alle zu regieren).

NP-hard

Intuitively, das sind die Probleme, die sind mindestens so hart wie die NP-vollständige Probleme . Beachten Sie, dass NP-harten Probleme nicht in NP sein und haben sie keine Entscheidungsprobleme sein.

Die genaue Definition hierbei ist, dass ein Problem X NP-hart ist, wenn es ein NP-vollständiges Problem Y ist, so dass Y reduzierbar ist in Polynomialzeit X .

Aber da jedes NP-vollständiges Problem kann zu jedem anderen NP-vollständigen Problem in polynomialer Zeit reduziert werden, alle NP-vollständigen Probleme können zu jedem NP-hard Problem in polynomialer Zeit reduziert werden. Dann wird, wenn es eine Lösung für ein NP-hartes Problem in polynomialer Zeit ist, gibt es eine Lösung für alle NP-Probleme in Polynomialzeit.

Beispiel:

Die Halteproblem ist ein NP-hard Problem. Das ist das Problem, das ein Programm P und Eingang I gegeben, wird es halt? Dies ist eine Entscheidung Problem, aber es ist nicht in NP. Es ist klar, dass jedes NP-vollständiges Problem auf diese reduziert werden kann. Als weiteres Beispiel ist jedes NP-vollständiges Problem NP-hart.

Meine Lieblings NP-vollständiges Problem ist die Sweeper Problem .

P = NP

Dies ist das bekannteste Problem in der Informatik, und eine der wichtigsten noch offenen Fragen in den mathematischen Wissenschaften. In der Tat ist das Ton Institute bietet eine Million Dollar für ein Lösung für das Problem (Stephen Cook writeup auf dem Sand Website ist recht gut ).

Es ist klar, dass P eine Teilmenge von NP ist. Die offene Frage ist, ob oder nicht NP-Probleme determinis Polynomzeit Lösungen haben. Es wird weitgehend angenommen, dass sie es nicht tun. Hier ist ein hervorragender kürzlich erschienener Artikel über die neueste (und die Bedeutung) des P = NP Problem: der Status des P-NP-Problem .

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

Andere Tipps

Ich habe mal umschauen und viele lange Erklärungen zu sehen. Hier ist ein kleines Diagramm, das nützlich sein kann zusammenfassen:

Beachten Sie, wie Schwierigkeitsgrad steigt von oben nach unten: alle NP NP-Complete reduziert werden und jedes NP-Complete können NP-Hard reduziert werden , die alle in P (Polynom) Zeit.

Wenn Sie eine schwierige Klasse von Problem in P Zeit lösen können, das bedeutet, gefunden, wie Sie alle leichten Probleme in P Zeit zu lösen (zum Beispiel P = NP beweisen, wenn Sie herausfinden, wie jede NP- zu lösen vollständiges Problem in P-Zeit).

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Hinweise zu Yes oder No Einträge:

* Ein NP-Problem, das auch P ist in P Zeit lösbar.
** Ein NP-Hard Problem, das auch NP-Complete ist nachprüfbar in P Zeit.
*** NP-vollständige Probleme (die alle eine Teilmenge von NP-hart bilden) sein könnte. Der Rest von NP schwer ist es nicht.

Ich fand auch dieses Diagramm ganz nützlich zu sehen, wie alle diese Arten einander entsprechen (mehr Aufmerksamkeit auf die linke Hälfte des Diagramms bezahlen).

Dies ist eine sehr informelle Antwort auf die gestellte Frage.

Kann 3233 als Produkt aus zwei anderen Zahlen geschrieben werden größer als 1? Gibt es eine Möglichkeit, einen Weg um alle von der Seven Bridges von Königs zu gehen, ohne wobei zweimal jede Brücke? Dies sind Beispiele für Fragen, die ein gemeinsames Merkmal teilen. Es ist vielleicht nicht offensichtlich sein, wie effizient die Antwort zu bestimmen, aber wenn die Antwort ‚Ja‘, dann gibt es ein kurzen und schnellen Beweis zu überprüfen. Im ersten Fall wird eine nicht-triviale Faktorisierung von 51; in den zweiten, eine Route für die Brücke Fuß (Einpassen der Randbedingung).

Entscheidungsproblem ist eine Sammlung von Fragen mit Ja oder Nein Antworten, die nur in einem Parameter variieren. Sprechen Sie das Problem COMPOSITE = { "Ist n composite": n eine ganze Zahl} oder EULERPATH = { "Hat der Graph G ein Euler-Pfad haben?": G ist ein endlicher Graph}.

Nun, verleihen einige Entscheidungsprobleme selbst effizient, wenn nicht auf der Hand Algorithmen. Euler entdeckte vor einen effizienten Algorithmus für Probleme wie der „Seven Bridges von Königsberg“ mehr als 250 Jahren.

Auf der anderen Seite, für viele Entscheidungsprobleme, es ist nicht klar, wie die Antwort zu bekommen - aber wenn Sie einige zusätzliche Information kennen, ist es offensichtlich, wie etwa gehen beweisen Sie die Antwort richtig haben. COMPOSITE ist wie folgt: Test Division der offensichtliche Algorithmus ist, und es ist langsam: eine 10-stellige Zahl Faktor, haben Sie so etwas wie 100.000 möglich Teilern versuchen. Aber wenn zum Beispiel jemand Ihnen gesagt, dass 61 ein Teiler von 3233, einfach langer Teilung ist ein effizienter Weg, um zu sehen, dass sie richtig sind.

Die Komplexitätsklasse NP die Klasse von Entscheidungsproblemen ist, wo die ‚Ja‘ Antworten auf Zustand kurz haben, schnell Beweise zu prüfen. Wie COMPOSITE. Ein wichtiger Punkt ist, dass diese Definition sagt nichts darüber, wie schwer das Problem ist. Wenn Sie eine korrekte und effiziente Möglichkeit haben, eine Entscheidung Problem zu lösen, nur die Schritte in der Lösung aufzuschreiben ist Beweis genug.

Algorithmen Forschung geht weiter, und neue clevere Algorithmen sind die ganze Zeit erstellt. Ein Problem, das Sie vielleicht nicht wissen, wie effizient lösen kann eine effiziente haben heute ausfallen (wenn nicht auf der Hand) Lösung von morgen. In der Tat dauerte es Forscher bis 2002 eine effiziente Lösung zu COMPOSITE zu finden! Mit all diesen Verbesserungen hat man wirklich fragen: Ist das etwas über mit kurzen Beweisen nur eine Illusion? Vielleicht alle Entscheidungsproblem, das sich für eine effiziente Beweise verleiht hat eine effiziente Lösung? Niemand weiß .

Vielleicht ist der größte Beitrag zu diesem Bereich kam mit der Entdeckung einer eigenartige Klasse von NP-Problemen. Durch das Spiel mit Schaltungsmodellen für die Berechnung, fand Stephen Cook eine Entscheidung Problem der NP-Sorte, die beweisbar so hart war oder härter als alle anderes NP-Problem. Eine effiziente Lösung für die boolean Erfüllbarkeitsproblem verwendet werden könnte, um eine effiziente zu erstellen Lösung jede andere Problem in NP. Bald darauf zeigte Richard Karp, dass eine Reihe von anderen Entscheidungsproblemen den gleichen Zweck dienen könnte. Diese Probleme in einem gewissen Sinne die "härteste" Probleme in NP, wurde bekannt als NP-vollständig Probleme.

Natürlich NP ist nur eine Klasse von Entscheidungsproblemen. Viele Probleme sind natürlich nicht auf diese Weise fest: „die Faktoren von N finden“, „findet den kürzesten Weg im Graphen G, das jede Ecke besucht“, „gibt einen Satz von Variablenzuweisungen, die der folgende Boolesche Ausdruck wahr macht“. Obwohl kann man informell talk über einige solche Probleme „in NP“ zu sein, technisch, das macht nicht viel Sinn - sie sind nicht Entscheidungsprobleme. Einige dieser Probleme haben könnten sogar die gleiche Art von Macht als NP-vollständige Problem: eine effiziente Lösung für diese (Nicht-Entscheidung) Probleme würde direkt zu einer effizienten Lösung für jedes NP-Problem führen. Ein Problem, wie das nennt man NP-hard .

Zusätzlich zu den anderen großen Antworten, hier ist die typisches Schema Menschen nutzen den Unterschied zwischen NP zu zeigen, NP-Complete, und NP-Hard:

eingeben Bild Beschreibung hier

P (Polynomial Zeit): Als Name schon sagt, das sind die Probleme, die in polynomieller Zeit gelöst werden können,

NP (nicht deterministisch-Polynom Zeit): Dies sind die Entscheidungsprobleme, die in Polynomialzeit prüft werden kann. Das heißt, wenn ich behaupte, dass es eine Polynomzeit Lösung für ein bestimmtes Problem ist, fragen Sie mich, es zu beweisen. Dann gebe ich Ihnen einen Beweis, die Sie leicht in polynomialer Zeit überprüfen können. Diese Art von Problemen sind NP-Probleme genannt. Man beachte, dass wir sprechen hier nicht darum, ob es eine Polynomzeit Lösung für dieses Problem ist oder nicht. Aber wir sprechen über die Lösung für ein bestimmtes Problem in polynomialer Zeit zu überprüfen.

NP-Hard: Dies sind mindestens so hart wie die schwierigsten Probleme in NP. Wenn wir diese Probleme in polynomialer Zeit lösen können, können wir jedes NP-Problem lösen, die möglicherweise vorhanden sein können. Beachten Sie, dass diese Probleme Probleme nicht notwendigerweise NP sind. Das heißt, können wir / kann-nicht die Lösung für diese Probleme in polynomialer Zeit verifizieren.

NP-Complete: Dies sind die Probleme, die sowohl NP und NP-Hard sind. Das heißt, wenn wir diese Probleme lösen können, wir anderes NP-Problem und die Lösungen für diese Probleme lösen können, können in polynomieller Zeit überprüft werden.

Der einfachste Weg, P v zu erklären. NP und solche ohne in technischen bekommen ist „Wort Probleme“ mit „Multiple-Choice-Problemen“ zu vergleichen.

Wenn Sie versuchen, ein „Wort-Problem“ zu lösen, müssen Sie die Lösung von Grund auf neu finden. Wenn Sie versuchen, ein „Multiple-Choice-Probleme“ zu lösen haben Sie die Wahl: entweder lösen Sie ihn wie ein „Wort-Problem“, oder versuchen, in jedem der Antworten auf sie gegeben stopfen, und den Kandidaten Antwort holen, das paßt.

Es kommt oft vor, dass ein „Multiple-Choice-Problem“ ist viel einfacher als das entsprechende „Wortproblem“. Die Kandidaten Antworten ersetzen und zu prüfen, ob sie wesentlich weniger Aufwand erfordern passen die richtige Antwort von Grund auf als der Suche nach

Wenn wir nun die Mühe zustimmen würden, die Polynomzeit „easy“, dann die Klasse P „easy Wort Probleme“ und die Klasse NP würde aus „einfachen Multiple-Choice-Problemen“.

nimmt würde aus .

Das Wesen der P v NP ist die Frage: „Gibt es einfache Probleme Multiple-Choice, der als Wort Probleme sind nicht einfach“? Das heißt, gibt es Probleme, für die es einfach ist, die Gültigkeit eines gegebenen Antwort zu überprüfen, aber die Antwort von Grund auf neu zu finden, ist schwierig?

Jetzt, da wir verstehen, intuitiv, was NP ist, müssen wir unsere Intuition herauszufordern. Es stellt sich heraus, dass es „Multiple-Choice-Probleme“ sind, dass in einem gewissen Sinne sind am schwersten von allen: wenn man eine Lösung für eines jener „am härtesten von allen“ Probleme finden würde würde man in der Lage sein, eine Lösung zu finden, um ALL NP-Probleme! Als Cook vor diesem 40 Jahren entdeckt kam es als eine völlige Überraschung. Diese „härteste von ihnen alle“ Probleme werden als NP-hard bekannt. Wenn Sie eine „Wort Problemlösung“ zu einem von ihnen finden Sie automatisch eine „Wort Problemlösung“ auf jeden und jedes „easy Multiple-Choice-Problem“!

finden würden

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

ich denke, wir es viel mehr kurz und bündig beantworten können. Ich antwortete eine bezogene Frage und Kopieren meiner Antwort von dort

Aber zuerst ein NP-hartes Problem ist ein Problem, für das wir nicht nachweisen können, dass eine Polynomzeit Lösung existiert. NP-Härte von einigen "Problem-P" ist in der Regel bewiesen durch ein bereits bewährtes NP-hard Problem mit dem "Problem-P" in Polynomzeit umgewandelt wird.

den Rest Frage zu beantworten, müssen Sie zuerst verstehen, welche NP-schwere Probleme sind auch NP-vollständig. Wenn ein NP-hard Problem NP setzen gehört, dann ist es NP-vollständig. Gehören NP zu setzen, um ein Problem sein muss

(i) ein Entscheidungsproblem,
  (Ii) die Anzahl der Lösungen für das Problem sollte endlich sein und jede Lösung von Polynomlänge sein sollte, und
  (Iii) gegeben eine Polynomlänge Lösung, sollten wir in der Lage sein zu sagen, ob die Antwort auf das Problem ist ja / nein

Nun ist es leicht zu sehen, dass es viele NP-schwere Probleme sein könnte, die gehören nicht NP zu setzen und sind schwerer zu lösen. Als intuitives Beispiel die Optimierung-Version von Handlungsreisende wo wir brauchen einen tatsächlichen Zeitplan zu finden ist schwieriger als die Entscheidungsversion Handlungsreisende wo wir müssen nur bestimmen, ob ein Zeitplan mit einer Länge von <= k existiert oder nicht.

NP-vollständige Probleme sind die Probleme, die sowohl NP-Hard und in der Komplexitätsklasse NP sind. Daher zeigen, dass ein gegebenes Problem NP-vollständig ist, müssen Sie zeigen, dass das Problem sowohl in NP ist und dass es NP-schwer ist.

Probleme, die in der NP-Komplexitätsklasse sind, können nicht-deterministisch in Polynomialzeit und eine mögliche Lösung gelöst werden (das heißt, ein Zertifikat) für ein Problem in NP für Korrektheit in Polynomzeit prüft werden.

Ein Beispiel für eine nicht-deterministische Lösung für das k-Clique Problem wäre so etwas wie:

1) zufällig ausgewählter k-Knoten aus einem Diagramm

2) überprüfen, ob diese k Knoten eine Clique bilden.

Die obige Strategie ist Polynom in der Größe des Eingabegraphen und damit das k-Clique Problem ist in NP.

Hinweis

, dass alle Probleme determinis auflösbar in Polynomzeit sind auch in NP.

Zeigen, dass ein Problem NP-schwer ist, umfasst in der Regel eine Reduktion von einem anderen NP-hard Problem für Ihr Problem einer Polynomzeit Mapping: http://en.wikipedia.org/wiki/Reduction_ (Komplexität)

Es gibt wirklich nette Antworten für diese Frage, so gibt es keinen Punkt meine eigene Erklärung zu schreiben. Also werde ich versuchen, mit einer ausgezeichneten Ressource über die verschiedenen Klassen von Rechenkomplexität beitragen.

Für jemanden, der glaubt, dass die Berechnungskomplexität nur über P und NP, hier ist die erschöpfende Ressource über die verschiedenen Komplexitätsprobleme . Abgesehen von Problemen durch OP gefragt, aufgeführt es etwa 500 verschiedene Klassen von Rechenproblemen mit schönen Beschreibungen und auch die Liste der Grundlagenforschung Papiere, die die Klasse beschreiben.

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

in NP
np-hard

- Intro. to Algorithms (3ed) durch Cormen, Leiserson, Rivest und Stein, S. 1069

Hier finden Sie einige interessante Defintion:

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow