Was ist ein NP-vollständig in der Informatik?

StackOverflow https://stackoverflow.com/questions/210829

Frage

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

War es hilfreich?

Lösung

NP steht für nicht-determinis Polynomial Zeit.

Das bedeutet, dass das Problem in polynomieller Zeit unter Verwendung eine nicht-deterministische Turingmaschine (wie eine normale Turing-Maschine, sondern auch ein nicht-deterministisch „Wahl“ -Funktion einschließlich) gelöst werden kann. Grundsätzlich muss eine Lösung sein, prüfbar in Poly Zeit. Wenn das der Fall ist, und ein bekanntes NP-Problem gelöst werden kann, das gegebene Problem mit modifizierten Eingang (ein NP-Problem kann sein, reduziert auf das gegebene Problem), dann ist das Problem NP abgeschlossen.

Die Hauptsache zu nehmen von einem NP-vollständigen Problem ist, dass es nicht in polynomialer Zeit in jeder bekannten Art und Weise gelöst werden kann. NP-Hard / NP-Complete ist eine Art und Weise zu zeigen, dass bestimmte Klassen von Problemen in realistischer Zeit nicht auflösbar sind.

Edit: Wie andere bereits festgestellt haben, gibt es oft Näherungslösungen für NP-vollständige Probleme. In diesem Fall gibt der Näherungslösung in der Regel eine Annäherung spezielle Notation gebunden mit, die uns sagt, wie nahe der Annäherung ist.

Andere Tipps

Was ist NP ?

NP ist die Menge aller Entscheidungsprobleme (Fragen mit einem Ja oder keine Antwort ), für den die ‚Ja'-Antworten können sein verifiziert in Polynomzeit (O (n k ) wobei n ist das Problem der Größe und k ist eine konstante) durch eine deterministische Turing-Maschine . Polynomzeit wird manchmal als die Definition von verwendet schnell oder schnell .

Was ist P ?

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

Was ist NP-Complete ?

Ein Problem, x, die in NP ist, ist auch in NP-Complete , wenn und nur wenn jedes anderes Problem in NP kann schnell sein (dh. In Polynomialzeit) in x umgewandelt.

Mit anderen Worten:

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

Also, was macht NP-Complete ist so interessant, dass, wenn einer der NP-vollständigen Probleme ist schnell gelöst wird, dann werden alle NP können Probleme gelöst werden schnell.

Siehe auch die Post Was ist „P = NP ?“, und warum es so eine berühmte Frage ist?

Was ist NP-Hard ?

NP-Hard sind Probleme, die mindestens so hart wie die schwierigsten Probleme in NP sind. Beachten Sie, dass NP-vollständige Probleme auch NP-hart sind. Allerdings sind nicht alle NP-harten Probleme sind NP (oder sogar ein Entscheidungsproblem), trotz NP als Präfix haben. Das ist der NP in NP-hard bedeutet nicht, nicht-deterministische Polynomialzeit . Ja, das ist verwirrend, aber seine Verwendung ist verschanzt und unwahrscheinlich zu ändern.

NP-Complete bedeutet etwas ganz Konkretes und Sie müssen vorsichtig sein, oder Sie werden die Definition falsch. Zunächst wird ein NP-Problem ist eine Ja / Nein Problem, dass

  1. Es ist polynomialzeit-Beweis für jede Instanz des Problems mit einem „Ja“ zu beantworten, dass die Antwort „ja“ lautet, oder (äquivalent)
  2. Es existiert ein Polynom-Algorithmus (möglicherweise Zufallsvariablen), die eine von Null verschiedene Wahrscheinlichkeit einer Antwort „Ja“ hat, wenn die Antwort auf eine Instanz des Problems „Ja“ und wird „nein“ sagen zu 100% die Zeit, wenn die Antwort „nein“. Mit anderen Worten muss der Algorithmus eine falsch-negative Rate von weniger als 100% und keine Fehlalarme.

Ein Problem X NP-vollständig, wenn

  1. X ist in NP, und
  2. Für jedes Problem Y in NP, gibt es eine „Reduktion“ von Y nach X: ein Polynom-Algorithmus, der jede Instanz von Y in eine Instanz von X transformiert, so dass die Antwort auf die Y-Instanz „ja“ wenn und nur wenn die Antwort X-Instanz ist „ja“.

Wenn X NP-vollständig ist und ein deterministischer, Polynom-Algorithmus besteht, dass alle Instanzen von X richtig lösen kann (0% falsch-positive, 0% falsch-negativ), dann jedes Problem in NP kann in deterministisch gelöst werden -polynomial Zeit (durch Reduktion zu X).

Bisher hat niemand mit einem solchen deterministischen Polynomialzeit-Algorithmus kommen, aber niemand hat sich als eine nicht existiert (es gibt eine Million Dollar für jeden, der entweder tun: das ist die P = NP Problem ). Das bedeutet nicht, dass Sie nicht eine bestimmte Instanz eines NP-Complete (oder NP-Hard) Problem lösen können. Es bedeutet nur, können Sie nicht etwas haben, das zuverlässig auf allen Instanzen eines Problems auf die gleiche Weise arbeiten Sie zuverlässig eine Liste von ganzen Zahlen sortiert werden können. Sie könnten sehr gut in der Lage sein, mit einem Algorithmus zu entwickeln, die auf allen praktischen Instanzen eines NP-Hard Problem sehr gut funktionieren werden.

NP-Complete ist eine Klasse von Problemen.

Die Klasse P besteht aus den Problemen, die in Polynomzeit auflösbar sind . Zum Beispiel könnten sie in O gelöst werden (n k ) für eine Konstante k, wobei n die Größe des Eingangs. Einfach gesagt, können Sie ein Programm schreiben, das in läuft vernünftig Zeit.

Die Klasse NP besteht aus den Problemen, die sind verifizierbar in polynomialer Zeit. Das heißt, wenn wir eine mögliche Lösung gegeben sind, dann können wir überprüfen, ob die gegebene Lösung richtig in Polynomialzeit ist.

Einige Beispiele sind die Boolesche Erfüllbarkeit (oder SAT ) Problem oder das Hamilton-Zyklus Problem. Es gibt viele Probleme, die in der Klasse NP bekannt sind.

NP-Complete bedeutet, das Problem ist, mindestens so hart wie irgendein Problem in NP.

Es ist wichtig, Informatik, weil es, dass jedes Problem in NP erwiesenermaßen sein transformierte in ein anderes Problem in NP-vollständig. Das bedeutet, dass eine Lösung für jedes einer NP-vollständige Problem ist eine Lösung für alle NP-Probleme.

Viele Algorithmen in Sicherheit ist abhängig von der Tatsache, dass keine bekannten Lösungen für NP schwer Probleme bestehen. Es wäre auf jeden Fall einen erheblichen Einfluss auf Computing hat, wenn eine Lösung gefunden werden.

Grundsätzlich ist dieser Probleme der Welt kann als

kategorisiert werden

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

1) Die erste ist keine Lösung für das Problem. 2) Das zweite ist die Notwendigkeit, exponentielle Zeit (dh O (2 ^ n), oben). 3) Die dritte ist die NP bezeichnet. 4) Die vierte ist einfach Problem.

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

.

NP: bezieht sich Polynomzeit noch eine Lösung zu finden. Wir sind nicht sicher, dass es keine Polynomzeit Lösung ist, aber wenn man eine Lösung bieten kann diese Lösung in polynomialer Zeit überprüft werden.

NP Complete: bezieht sich in Polynomzeit uns noch noch eine Lösung zu finden, aber es kann in polynomieller Zeit überprüft werden. Das Problem NPC in NP ist das schwierigere Problem, so dass, wenn wir nachweisen können, dass wir P Lösung NPC Problem dann NP-Probleme haben, die in P-Lösung gefunden werden können.

NP Hard: bezieht sich Polynomzeit noch ist es, eine Lösung zu finden, aber es ist sicher nicht in der Lage in Polynomzeit prüft werden. NP Hart Problem übertrifft NPC Schwierigkeiten.

Es ist eine Klasse von Problemen, wo wir jede Möglichkeit sicher sein, simulieren müssen wir die optimale Lösung.

Es gibt viele gute Heuristik für einige NP-vollständige Probleme, aber sie sind nur eine Vermutung am besten.

Wenn Sie sich für ein Beispiel eines NP-vollständiges Problem suchen, dann empfehle ich Ihnen einen Blick auf 3-SAT .

Die Grundvoraussetzung ist, dass Sie einen Ausdruck in konjunktive Normalform haben, das ist eine Möglichkeit, Sie sagen von RUP eine Reihe von Ausdrücken verbunden haben, dass alles wahr sein müssen: 

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

Das 3-SAT Problem ist es, eine Lösung zu finden, die die Expression gerecht wird, wo jedes der ODER-Ausdrücke hat genau 3 booleans übereinstimmen: 

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

Eine Lösung dieses man könnte sein (a = T b = T, c = F, D = F). Es wurde jedoch kein Algorithmus entdeckt, dass dieses Problem im allgemeinen Fall in polynomialer Zeit lösen wird. Das bedeutet, dass der beste Weg, um dieses Problem zu lösen, im Wesentlichen einen Brute-Force-guess-and-Check zu tun ist, und verschiedene Kombinationen ausprobieren, bis Sie einen finden, das funktioniert.

Was ist das Besondere an der 3-SAT Problem ist, dass alle NP-vollständiges Problem zu einem Problem 3-SAT reduziert werden kann. Dies bedeutet, dass, wenn Sie einen Polynomialzeit-Algorithmus zu finden, dieses Problem zu lösen, dann erhalten Sie $ 1.000.000 , auf der ganzen Welt nicht den Respekt und die Bewunderung von Informatikern und Mathematikern zu nennen.

Ehrlich gesagt, Wikipedia könnte der beste Ort, um eine Antwort auf diese zu suchen.

Wenn NP = P, dann können wir sehr harte Probleme lösen viel schneller als wir dachten, wir könnten vor. Wenn wir nur ein NP-vollständige Problem in P (Polynom) Zeit zu lösen, dann kann es auch für alle anderen Probleme in der NP-Complete Kategorie angewandt werden.

Wir brauchen Algorithmen und Probleme zu trennen. Wir schreiben Algorithmen Probleme zu lösen, und sie skaliert auf eine bestimmte Weise in. Obwohl dies eine Vereinfachung ist, lassen Sie uns einen Algorithmus mit einem ‚P‘ kennzeichnen, wenn die Skalierung gut genug ist, und ‚NP‘, wenn es nicht ist.

Es ist hilfreich zu wissen, die Dinge, über die Probleme versuchen wir zu lösen, anstatt die Algorithmen verwenden wir diese zu lösen. Also werden wir sagen, dass alle Probleme, die eine gut Skalierungsalgorithmus haben, sind „in P“. Und diejenigen, die eine schlechte Skalierungsalgorithmus haben, sind „in NP“.

Das bedeutet, dass viele einfache Probleme „in NP“ sind auch, weil wir schlechte Algorithmen schreiben können leicht Probleme zu lösen. Es wäre gut, zu wissen, welche Probleme in NP die wirklich tricky ones sind, aber wir wollen nicht nur sagen: „Es ist die, die wir haben keinen guten Algorithmus für“. Schließlich habe ich mit einem Problem kommen konnte (nennen wir es X), dass ich denke, braucht ein Super-erstaunlichen Algorithmus. Ich sage der Welt, dass der beste Algorithmus ich einfiel zu lösen X schlecht skaliert, und so denke ich, dass X ein wirklich schwieriges Problem ist. Aber morgen, vielleicht jemand schlauer als ich einen Algorithmus erfindet die X löst und ist in P. Das ist also nicht eine sehr gute Definition für schwere Probleme.

Immerhin gibt es viele Probleme in NP, dass niemand einen guten Algorithmus für weiß. Also, wenn ich könnte beweisen , dass X eine bestimmte Art von Problem ist: ein, wo ein guter Algorithmus X zu lösen, könnte auch verwendet werden, in einigen Umwegen, einen guten zu geben Algorithmus für alle anderes Problem in NP. Nun könnten die Menschen ein bisschen mehr davon überzeugt sein, dass X ein wirklich schwieriges Problem. Und in diesem Fall nennen wir X NP-vollständig.

Die Definitionen für NP vollständige Probleme oben ist richtig, aber ich dachte, ich könnte über ihre philosophische Bedeutung lyrische Wachs als noch niemand dieses Thema angesprochen hat.

Fast alle komplexen Probleme Sie stoßen wird NP abgeschlossen. Es ist etwas sehr Grundlegendes über diese Klasse, und das scheint nur aus leicht lösbaren Problemen rechen anders zu sein. Sie Art haben ihren eigenen Geschmack, und es ist nicht so schwer, sie zu erkennen. Das bedeutet im Wesentlichen, dass jeder mäßig komplexer Algorithmus ist unmöglich für Sie genau zu lösen -. Planung, Optimierung, Verpackung, Abdeckung usw.

Aber nicht alles verloren ist, wenn ein Problem auftreten werde, ist NP abgeschlossen. Es gibt einen großen und sehr technischen Bereich, wo die Menschen Approximationsalgorithmen studieren, die Sie Garantien für die Lösung eines NP vollständigen Problems nahe zu sein. Einige davon sind unglaublich starke Garantien - zum Beispiel für 3sat, Sie eine 7/8 Garantie durch einen wirklich offensichtlich Algorithmus bekommen. Noch besser ist, in Wirklichkeit gibt es einige sehr starke Heuristiken, die bei, dass große Antworten treffen (aber keine Garantie!) Für diese Probleme.

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

Ich habe eine Erklärung gehört, das heißt:“ NP-Vollständigkeits ist wahrscheinlich eine der rätselhaften Ideen in der Studie von Algorithmen. „NP“ steht für „nicht deterministisch polynomialer Zeit“ und ist der Name für das, was eine Komplexitätsklasse genannt wird, auf die Probleme gehören. Das Wichtigste über die NP Komplexitätsklasse ist, dass Probleme innerhalb dieser Klasse können sein prüft durch eine Polynomialzeitalgorithmus. Als Beispiel betrachten wir das Problem Sachen zu zählen. Angenommen, es gibt ein Bündel von Äpfeln auf einem Tisch. Das Problem ist: „Wie viele Äpfel gibt es?“ Sie sind mit einer möglichen Antwort gegeben, 8. Sie diese Antwort in polynomialer Zeit unter Verwendung des Algorithmus von verifizieren können, duh, die Äpfel zu zählen. Zählen geschieht, die Äpfel in O (n) (das ist Big-O-Notation) Zeit, weil es einen Schritt nimmt jeden Apfel zu zählen. Für n Äpfel, müssen Sie n Schritte. Dieses Problem ist in der NP-Komplexitätsklasse.

Ein Problem wird beschrieben als: NP-vollständig , wenn nachgewiesen werden kann, dass es beide ist NP-Hard und verifizierbar in polynomialer Zeit. Ohne zu tief in die Diskussion von NP-Hard, es genügt zu sagen, dass es bestimmte Probleme zu denen Polynomzeit Lösungen nicht gefunden worden. Das heißt, es dauert so etwas wie n! Schritte (n Fakultät), sich zu lösen. Wenn Sie jedoch eine Lösung für ein NP-vollständiges Problem gegeben sind, können Sie es in polynomialer Zeit verifizieren.

Ein klassisches Beispiel für ein NP-vollständiges Problem ist das Reisen Salesman Problem. "

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

NP Problem: -

  1. NP-Problem ist solches Problem, das in nicht-deterministisch polynomialer Zeit gelöst werden kann.
  2. Non deterministischer Algorithmus arbeitet in zweistufiger.
  3. Non determinis Erraten Stufe && Nicht deterministisch Verifikationsstufe.

Typ Np Problem

  1. NP komplett
  2. NP Fest

NP vollständiges Problem: -

1 Die Entscheidung Problem A heißt vollständig NP, wenn es nach zwei Eigenschaften hat: -

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

Einige Ex: -

  • Knapsackproblem
  • Unter gesetzt Summe Problem
  • Vertex Abdeckung Problem

NP-vollständige Probleme sind eine Reihe von Problemen zu denen jeweils jedem anderes NP-Problem kann in polynomieller Zeit reduziert werden, und deren Lösung kann noch in Polynomzeit prüft werden. Das heißt, jedes NP-Problem sein in eine der NP-vollständigen Problemen umgewandelt. - Informell, ein NP-vollständiges Problem ist ein NP-Problem, das zumindest als „hart“ ist wie jedes andere Problem in NP.

ein NP-Problem ist ein, wo ein Computer-Algorithmus, die eine Lösung überprüft in Polynomzeit erstellt werden kann.

ein NP-vollständiges Problem ist NP, aber wenn auch Sie es in polynomialer Zeit (genannt P) lösen dann alle NP-Probleme sind P.

So erhalten crackin'.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top