Was ist ein NP-Complete in der Informatik?

Was ist ein NP-vollständiges Problem? Warum ist es so ein wichtiges Thema in der Informatik?

NP steht für nicht deterministische Polynomzeit .

Dies bedeutet, dass das Problem in Polynomzeit mit einer nicht deterministischen Turing-Maschine gelöst werden kann (wie eine normale Turing-Maschine, aber auch mit einer nicht deterministischen "Auswahl" -Funktion). Grundsätzlich muss eine Lösung in Poly-Zeit testbar sein. Wenn dies der Fall ist und ein bekanntes NP-Problem unter Verwendung des gegebenen Problems mit modifizierter Eingabe gelöst werden kann (ein NP-Problem kann auf das gegebene Problem reduziert werden ), ist das Problem NP-vollständig.

Die Hauptsache, um ein NP-vollständiges Problem zu beseitigen, ist, dass es in keiner bekannten Weise in Polynomzeit gelöst werden kann. Mit NP-Hard / NP-Complete kann gezeigt werden, dass bestimmte Problemklassen in realistischer Zeit nicht lösbar sind.

Bearbeiten: Wie andere angemerkt haben, gibt es häufig ungefähre Lösungen für NP-Complete-Probleme. In diesem Fall ergibt die Näherungslösung normalerweise eine Näherungsgrenze unter Verwendung einer speziellen Notation, die uns sagt, wie nahe die Näherung ist.

Was ist NP ?

NP ist die Menge aller Entscheidungsprobleme (Fragen mit einer Ja- oder Nein-Antwort), für die die Ja-Antworten in Polynomzeit (O (n ^k ) verifiziert werden können, wobei n die Problemgröße ist und k a ist konstant) durch eine deterministische Turingmaschine . Die Polynomzeit wird manchmal als Definition von schnell oder schnell verwendet .

Was ist P. ?

P ist die Menge aller Entscheidungsprobleme, die durch eine deterministische Turing-Maschine in Polynomzeit gelöst werden können . Da sie in Polynomzeit gelöst werden können, können sie auch in Polynomzeit verifiziert werden. Daher ist P eine Teilmenge von NP.

Was ist NP-Complete ?

Ein Problem x, das in NP ist, ist auch dann in NP-Complete, wenn und nur wenn jedes andere Problem in NP schnell (dh in Polynomzeit) in x umgewandelt werden kann.

Mit anderen Worten:

1. x ist in NP und
2. Jedes Problem in NP ist auf x reduzierbar

Was NP-Complete so interessant macht, ist, dass, wenn eines der NP-Complete-Probleme schnell gelöst werden sollte, alle NP Probleme schnell gelöst werden können.

Siehe auch den Beitrag Was ist "P = NP?" Und warum ist es eine so berühmte Frage?

Was ist NP-schwer ?

NP-Hard sind Probleme, die mindestens so schwer sind wie die schwersten Probleme in NP. Beachten Sie, dass NP-Complete-Probleme auch NP-schwer sind. Allerdings sind nicht alle NP-harten Probleme NP (oder sogar ein Entscheidungsproblem), obwohl sie NPein Präfix haben. Das heißt, der NP in NP-hard bedeutet nicht nicht deterministische Polynomzeit . Ja, das ist verwirrend, aber seine Verwendung ist fest verankert und wird sich wahrscheinlich nicht ändern.

NP-Complete bedeutet etwas sehr Spezifisches und Sie müssen vorsichtig sein, sonst wird die Definition falsch. Erstens ist ein NP-Problem ein Ja / Nein-Problem, so dass

1. Für jede Instanz des Problems gibt es einen Polynomzeitbeweis mit der Antwort "Ja", dass die Antwort "Ja" oder (äquivalent) lautet.
2. Es gibt einen Polynom-Zeit-Algorithmus (möglicherweise unter Verwendung von Zufallsvariablen), der eine Wahrscheinlichkeit ungleich Null hat, mit "Ja" zu antworten, wenn die Antwort auf eine Instanz des Problems "Ja" lautet und in 100% der Fälle "Nein" sagt, wenn Die Antwort ist nein." Mit anderen Worten, der Algorithmus muss eine falsch-negative Rate von weniger als 100% und keine falsch-positiven aufweisen.

Ein Problem X ist NP-Complete wenn

1. X ist in NP und
2. Für jedes Problem Y in NP gibt es eine "Reduktion" von Y auf X: einen Polynom-Zeit-Algorithmus, der jede Instanz von Y in eine Instanz von X umwandelt, so dass die Antwort auf die Y-Instanz genau dann "Ja" lautet wenn die Antwort X-Instanz "Ja" ist.

Wenn X NP-vollständig ist und ein deterministischer Polynom-Zeit-Algorithmus existiert, der alle Instanzen von X korrekt lösen kann (0% falsch-positive, 0% falsch-negative), kann jedes Problem in NP in deterministisch-polynomial gelöst werden. Zeit (durch Reduktion auf X).

Bisher hat niemand einen solchen deterministischen Polynom-Zeit-Algorithmus entwickelt, aber niemand hat bewiesen, dass es keinen gibt (es gibt eine Million Dollar für jeden, der beides kann: das ist das P = NP-Problem ). Das bedeutet nicht, dass Sie eine bestimmte Instanz eines NP-Complete- (oder NP-Hard-) Problems nicht lösen können. Es bedeutet nur, dass Sie nicht über etwas verfügen können, das in allen Fällen eines Problems zuverlässig funktioniert, genauso wie Sie eine Liste von Ganzzahlen zuverlässig sortieren können. Möglicherweise können Sie einen Algorithmus entwickeln, der in allen praktischen Fällen eines NP-Hard-Problems sehr gut funktioniert.

Grundsätzlich können die Probleme dieser Welt als kategorisiert werden

         1) Unlösbares Problem 2) Unlösbares Problem 3) NP-Problem 4) P-Problem

         1) Der erste ist keine Lösung für das Problem. 2) Die zweite ist die exponentielle Bedarfszeit (dh O (2 ^ n) oben). 3) Der dritte heißt NP. 4) Das vierte ist ein einfaches Problem.

P: bezieht sich auf eine Lösung des Problems der Polynomzeit.

NP: bezieht sich auf die Polynomzeit, um noch eine Lösung zu finden. Wir sind uns nicht sicher, ob es keine Polynomial Time-Lösung gibt. Sobald Sie jedoch eine Lösung bereitgestellt haben, kann diese Lösung in Polynomial Time überprüft werden.

NP abgeschlossen: Bezieht sich auf die Polynomzeit. Wir haben noch keine Lösung gefunden, diese kann jedoch in der Polynomzeit überprüft werden. Das Problem NPC in NP ist das schwierigere Problem. Wenn wir also beweisen können, dass wir eine P-Lösung für das NPC-Problem haben, dann können NP-Probleme in P-Lösung gefunden werden.

NP Hard: verweist darauf, dass die Polynomzeit noch keine Lösung gefunden hat, aber in der Polynomzeit sicher nicht verifiziert werden kann. NP Hard Problem übertrifft NPC Schwierigkeit.

NP-Complete ist eine Klasse von Problemen.

Die Klasse Pbesteht aus den Problemen, die in Polynomzeit lösbar sind . Zum Beispiel könnten sie in O (n ^k ) für eine Konstante k gelöst werden , wobei n die Größe der Eingabe ist. Einfach ausgedrückt, können Sie ein Programm schreiben, das in angemessener Weise ausgeführt wird Zeit ausgeführt wird.

Die Klasse NPbesteht aus den Problemen, die überprüfbar sind in der Polynomzeit sind. Das heißt, wenn wir eine mögliche Lösung erhalten, können wir überprüfen, ob die gegebene Lösung in der Polynomzeit korrekt ist.

Einige Beispiele sind das Boolean Satisfiability (oder SAT ) -Problem oder das Hamilton-Zyklus-Problem. Es gibt viele Probleme, von denen bekannt ist, dass sie in der Klasse NP liegen.

NP-Completebedeutet, dass das Problem zumindest ist so schwer ist wie jedes Problem in NP.

Es ist wichtig, Informatik , weil es , dass jedes Problem in NP nachgewiesen worden ist verwandelt in ein anderes Problem in NP-vollständig. Das bedeutet, dass eine Lösung für ein NP-vollständiges Problem eine Lösung für alle NP-Probleme ist.

Viele Sicherheitsalgorithmen hängen von der Tatsache ab, dass keine bekannten Lösungen für NP-Probleme existieren. Wenn eine Lösung gefunden würde, hätte dies definitiv erhebliche Auswirkungen auf die Datenverarbeitung.

Es ist eine Klasse von Problemen, bei denen wir jede Möglichkeit simulieren müssen, um sicherzugehen, dass wir die optimale Lösung haben.

Es gibt viele gute Heuristiken für einige NP-Complete-Probleme, aber sie sind bestenfalls eine fundierte Vermutung.

Wenn Sie nach einem Beispiel für ein NP-vollständiges Problem suchen, sollten Sie sich 3-SAT ansehen .

Die Grundvoraussetzung ist, dass Sie einen Ausdruck in konjunktiver Normalform haben. Dies bedeutet, dass Sie eine Reihe von Ausdrücken haben, die durch OPs verbunden sind, die alle wahr sein müssen:

(a or b) and (b or !c) and (d or !e or f) ...

Das 3-SAT-Problem besteht darin, eine Lösung zu finden, die den Ausdruck erfüllt, bei dem jeder der OR-Ausdrücke genau 3 Boolesche Werte aufweist:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Eine Lösung für dieses Problem könnte sein (a = T, b = T, c = F, d = F). Es wurde jedoch kein Algorithmus entdeckt, der dieses Problem im allgemeinen Fall in Polynomzeit lösen könnte. Dies bedeutet, dass der beste Weg, um dieses Problem zu lösen, darin besteht, im Wesentlichen eine Brute-Force-Vermutung durchzuführen und verschiedene Kombinationen auszuprobieren, bis Sie eine finden, die funktioniert.

Das Besondere am 3-SAT-Problem ist, dass JEDES NP-vollständige Problem auf ein 3-SAT-Problem reduziert werden kann. Das heißt, wenn Sie einen Polynom-Zeit-Algorithmus finden, um dieses Problem zu lösen, erhalten Sie 1.000.000 US-Dollar , ganz zu schweigen vom Respekt und der Bewunderung von Informatikern und Mathematikern auf der ganzen Welt.

Ehrlich gesagt, Wikipedia könnte der beste Ort sein, um nach einer Antwort darauf zu suchen.

Wenn NP = P, können wir sehr schwierige Probleme viel schneller lösen, als wir vorher dachten. Wenn wir nur ein NP-Complete-Problem in P-Zeit (Polynom) lösen, kann es auf alle anderen Probleme in der NP-Complete-Kategorie angewendet werden.

Wir müssen Algorithmen und Probleme trennen. Wir schreiben Algorithmen, um Probleme zu lösen, und sie skalieren auf eine bestimmte Weise. Obwohl dies eine Vereinfachung ist, kennzeichnen wir einen Algorithmus mit einem 'P', wenn die Skalierung gut genug ist, und mit 'NP', wenn dies nicht der Fall ist.

Es ist hilfreich, Dinge über die Probleme zu wissen, die wir zu lösen versuchen, und nicht über die Algorithmen, mit denen wir sie lösen. Wir werden also sagen, dass alle Probleme, die einen gut skalierenden Algorithmus haben, "in P" sind. Und diejenigen, die einen Algorithmus mit schlechter Skalierung haben, sind "in NP".

Das bedeutet, dass viele einfache Probleme auch "in NP" sind, weil wir schlechte Algorithmen schreiben können, um einfache Probleme zu lösen. Es wäre gut zu wissen, welche Probleme in NP wirklich schwierig sind, aber wir möchten nicht nur sagen, "es sind diejenigen, für die wir keinen guten Algorithmus gefunden haben". Schließlich könnte ich mir ein Problem einfallen lassen (nennen wir es X), das meiner Meinung nach einen super erstaunlichen Algorithmus benötigt. Ich sage der Welt, dass der beste Algorithmus, den ich finden könnte, um X-Skalen schlecht zu lösen, und deshalb denke ich, dass X ein wirklich schwieriges Problem ist. Aber morgen erfindet vielleicht jemand, der klüger als ich ist, einen Algorithmus, der X löst und in P ist. Dies ist also keine sehr gute Definition für schwierige Probleme.

Trotzdem gibt es in NP viele Probleme, für die niemand einen guten Algorithmus kennt. Also , wenn ich könnte beweisen , dass X eine bestimmte Art von Problem ist: ein , wo ein guter Algorithmus zu lösen X könnte auch verwendet werden, in einigen Umwegen sein, einen guten Algorithmus zu geben jedes anderes Problem in NP. Nun, die Leute sind vielleicht ein bisschen mehr davon überzeugt, dass X ein wirklich kniffliges Problem ist. Und in diesem Fall nennen wir X NP-Complete.

Die obigen Definitionen für NP-Komplettprobleme sind korrekt, aber ich dachte, ich könnte über ihre philosophische Bedeutung lyrisch werden, da noch niemand dieses Problem angesprochen hat.

Fast alle komplexen Probleme, auf die Sie stoßen, sind NP Complete. Diese Klasse hat etwas sehr Grundlegendes und scheint sich nur rechnerisch von leicht lösbaren Problemen zu unterscheiden. Sie haben irgendwie ihren eigenen Geschmack und es ist nicht so schwer, sie zu erkennen. Dies bedeutet im Grunde, dass Sie keinen mäßig komplexen Algorithmus genau lösen können - planen, optimieren, verpacken, abdecken usw.

Aber nicht alles ist verloren, wenn ein Problem, auf das Sie stoßen, NP Complete ist. Es gibt ein weites und sehr technisches Gebiet, in dem Menschen Näherungsalgorithmen studieren, die Ihnen Garantien dafür geben, dass Sie der Lösung eines NP-Komplettproblems nahe kommen. Einige davon sind unglaublich starke Garantien - zum Beispiel können Sie für 3sat eine 7/8-Garantie durch einen wirklich offensichtlichen Algorithmus erhalten. Noch besser ist, dass es in der Realität einige sehr starke Heuristiken gibt, die hervorragende Antworten (aber keine Garantien!) Auf diese Probleme liefern.

Beachten Sie, dass zwei sehr bekannte Probleme - Graphisomorphismus und Factoring - nicht als P oder NP bekannt sind.

Ich habe eine Erklärung gehört, nämlich: "NP-Vollständigkeit ist wahrscheinlich eine der rätselhafteren Ideen bei der Untersuchung von Algorithmen." NP "steht für" nichtdeterministische Polynomzeit "und ist der Name für eine sogenannte Komplexitätsklasse Welche Probleme gehören können? Das Wichtige an der NP- Komplexitätsklasse ist, dass Probleme innerhalb dieser Klasse überprüft werden könnendurch einen Polynomzeitalgorithmus. Betrachten Sie als Beispiel das Problem des Zählens. Angenommen, auf einem Tisch liegen ein paar Äpfel. Das Problem ist "Wie viele Äpfel gibt es?" Sie erhalten eine mögliche Antwort: 8. Sie können diese Antwort in Polynomzeit überprüfen, indem Sie den Algorithmus von, duh, Zählen der Äpfel verwenden. Das Zählen der Äpfel erfolgt in O (n) -Zeit (das ist Big-oh-Notation), da es einen Schritt dauert, jeden Apfel zu zählen. Für n Äpfel benötigen Sie n Schritte. Dieses Problem liegt in der NP-Komplexitätsklasse.

Ein Problem wird als NP-vollständig klassifiziert, wenn gezeigt werden kann, dass es sowohl NP-hart als auch in der Polynomzeit überprüfbar ist . Ohne zu tief in die Diskussion von NP-Hard einzusteigen, genügt es zu sagen, dass es bestimmte Probleme gibt, für die keine polynomiellen Zeitlösungen gefunden wurden. Das heißt, es dauert so etwas wie n! (n faktorielle) Schritte, um sie zu lösen. Wenn Sie jedoch eine Lösung für ein NP-Complete-Problem erhalten, können Sie diese in Polynomzeit überprüfen.

Ein klassisches Beispiel für ein NP-Complete-Problem ist das Travelling Salesman Problem. "

Der Autor: ApoxyButt Von: http://www.everything2.com/title/NP-complete

NP Problem: -

1. NP-Probleme sind solche Probleme, die in nicht deterministischer Polynomzeit gelöst werden können.
2. Nicht deterministische Algorithmen arbeiten in zwei Stufen.
3. Nicht deterministische Vermutungsphase && Nicht deterministische Überprüfungsphase.

Art des Np-Problems

1. NP komplett
2. NP Hard

NP Komplettes Problem: -

1 Entscheidungsproblem A heißt NP vollständig, wenn es die folgenden zwei Eigenschaften hat:

1. Es gehört zur Klasse NP.
2. Jedes andere Problem in NP kann in Polynomzeit in P umgewandelt werden.

Einige Ex: -

• Rucksackproblem
• Teilmenge Summenproblem
• Scheitelpunktabdeckungsproblem

NP-vollständige Probleme sind eine Reihe von Problemen, auf die jedes andere NP-Problem in der Polynomzeit reduziert werden kann und deren Lösung in der Polynomzeit noch verifiziert werden kann. Das heißt, jedes NP-Problem kann in jedes der NP-vollständigen Probleme umgewandelt werden. - Informell ist ein NP-vollständiges Problem ein NP-Problem, das mindestens so "hart" ist wie jedes andere Problem in NP.

So weit ich das verstehe

P ist die Menge von Problemen, die in Polynomzeit mit einem deterministischen TM gelöst werden könnten.

NP ist die Menge von Problemen, die ein nicht deterministisches TM erfordern, um in Polynomzeit gelöst zu werden. Dies bedeutet, alle möglichen Variablen parallel zu überprüfen, wobei jede Instanz Polynomzeit benötigt. Wenn das Problem lösbar ist, muss mindestens einer dieser parallelen Zustände die Lösung für das Problem haben. Dies bedeutet auch, dass Sie, wenn Sie eine Vermutung über die Lösungsvariablen angestellt haben, nur die Gültigkeit der Lösung in Polynomzeit überprüfen müssen.

NP-Hard ist die Menge, bei der Probleme mindestens so schwer sind wie NP. Jedes Problem in NP könnte in der Polynomzeit in ein NP-hartes Problem umgewandelt werden. Diese Probleme können nicht in Polynomzeit gelöst werden, wenn P nicht gleich NP ist. Das heißt, wenn das schwierigste Problem in NP die Polynomzeit lösbar ist, dann sind nur NP-harte Probleme die Polynomzeit lösbar.

NP-Complete ist die Schnittmenge von NP und NP-Hard. Jedes NP-Problem könnte in Polynomzeit in ein NP-vollständiges Problem umgewandelt werden. Das heißt, wenn einer der NP-Complete eine effiziente Lösung haben könnte, könnte jedes NP-Problem mit der gleichen Effizienz gelöst werden.

Bitte lassen Sie mich wissen, wenn ich einen Fehler gemacht habe.

Ein NP-Problem ist ein Problem, bei dem ein Computeralgorithmus, der eine Lösung überprüft, in Polynomzeit erstellt werden kann.

Ein NP-vollständiges Problem ist NP, aber auch wenn Sie es in Polynomzeit (genannt P) lösen können, sind alle NP-Probleme P.

Also los geht's.