Was ist eine NP-Vollendung in der Informatik?

Question

Was ist ein NP-komplettes Problem? Warum ist es ein so wichtiges Thema in der Informatik?

Answer 1

Was ist NP ?

NP ist die Menge aller Entscheidungsprobleme (Fragen mit einer Ja-oder-Nein-Antwort), bei denen die "Ja"-Antworten sein können verifiziert in polynomieller Zeit (O(n k ) wobei n ist die Problemgröße und k ist eine Konstante) durch a deterministische Turing-Maschine . Die Polynomzeit wird manchmal als Definition von schnell o schnell .

Was ist P ?

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

Was ist NP-komplett ?

Ein Problem x, das in NP ist, ist auch in NP-Complete wenn und nur wenn jedes andere NP-Problem kann schnell (d.h. in polynomieller Zeit) in x transformiert werden.

Mit anderen Worten:

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

Was macht also NP-komplett so interessant ist, dass, wenn eines der NP-kompletten Probleme schnell gelöst werden könnte, alle NP Probleme schnell gelöst werden können.

Siehe auch den Beitrag Was bedeutet "P=NP?", und warum ist diese Frage so berühmt?

Was ist NP-Hard ?

NP-schwer sind Probleme, die mindestens so schwer sind wie die schwersten Probleme in NP. Beachten Sie, dass NP-vollständige Probleme auch NP-hart sind. Allerdings sind nicht alle NP-schweren Probleme NP (oder sogar ein Entscheidungsproblem), obwohl sie NP als Präfix. Das heißt, die NP in NP-hart bedeutet nicht nicht-deterministische Polynomialzeit . Ja, das ist verwirrend, aber die Verwendung ist fest etabliert und wird sich wahrscheinlich nicht ändern.

Answer 2

NP steht für Nicht-deterministisch Polynom Zeit.

Das bedeutet, dass das Problem in Polynomialzeit mit einer nichtdeterministischen Turing-Maschine (wie eine normale Turing-Maschine, aber mit einer nichtdeterministischen "Wahl"-Funktion) gelöst werden kann. Im Grunde muss eine Lösung sein prüfbar in Polyzeit. Wenn das der Fall ist und ein bekanntes NP-Problem mit Hilfe des gegebenen Problems mit veränderter Eingabe gelöst werden kann (ein NP-Problem kann reduziert für das gegebene Problem), dann ist das Problem NP-vollständig.

Das Wichtigste, was man von einem NP-kompletten Problem mitnehmen kann, ist, dass es auf keine bekannte Weise in polynomieller Zeit gelöst werden kann. NP-Hard/NP-Complete ist eine Methode, um zu zeigen, dass bestimmte Klassen von Problemen nicht in realistischer Zeit lösbar sind.

Edit: Wie bereits von anderen erwähnt, gibt es oft Näherungslösungen für NP-komplette Probleme. In diesem Fall gibt die Näherungslösung in der Regel eine Näherungsschranke mit einer speziellen Notation, die uns sagt, wie nahe die Näherung ist.

Answer 3

Grundsätzlich lassen sich die Probleme dieser Welt in folgende Kategorien einteilen

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

---

         1) Die erste Variante ist keine Lösung für das Problem.          2)Die zweite ist der Bedarf an exponentieller Zeit (d.h. O (2 ^ n) oben).          3)Die dritte wird NP genannt.          4)Das vierte ist ein einfaches Problem.

---

P: bezieht sich auf eine Lösung des Problems in Polynomialzeit.

NP: verweist auf Polynomialzeit, um eine Lösung zu finden. Wir sind nicht sicher, dass es keine Lösung in Polynomialzeit gibt, aber sobald Sie eine Lösung anbieten, kann diese Lösung in Polynomialzeit überprüft werden.

NP Complete: verweist in Polynomial Time wir noch eine Lösung zu finden, aber es kann in Polynomial Time überprüft werden. Das Problem NPC in NP ist das schwierigere Problem, so dass, wenn wir beweisen können, dass wir P Lösung für NPC Problem haben, dann NP Probleme, die in P Lösung gefunden werden kann.

NP Hard: verweist auf Polynomial Time ist noch eine Lösung zu finden, aber es ist sicher nicht in der Lage, in Polynomial Time überprüft werden. NP Hard Problem übertrifft NPC Schwierigkeit.

Answer 4

NP-Complete bedeutet etwas sehr Spezielles und man muss vorsichtig sein, sonst versteht man die Definition falsch. Erstens ist ein NP-Problem ein Ja/Nein-Problem, bei dem

1. Für jeden Fall des Problems mit einer "Ja"-Antwort gibt es einen Polynomialbeweis, dass die Antwort "Ja" ist, oder (äquivalent)
2. Es gibt einen Polynomialzeit-Algorithmus (möglicherweise unter Verwendung von Zufallsvariablen), der mit einer Wahrscheinlichkeit ungleich Null mit "Ja" antwortet, wenn die Antwort auf eine Instanz des Problems "Ja" lautet, und der in 100 % der Fälle "Nein" sagt, wenn die Antwort "Nein" lautet. Mit anderen Worten: Der Algorithmus muss eine Falsch-Negativ-Rate von weniger als 100 % und keine Falsch-Positive haben.

Ein Problem X ist NP-komplett, wenn

1. X ist in NP, und
2. Für jedes Problem Y in NP gibt es eine "Reduktion" von Y nach X: einen Polynomialzeit-Algorithmus, der jede Instanz von Y in eine Instanz von X umwandelt, so dass die Antwort auf die Y-Instanz "ja" ist, wenn und nur wenn die Antwort X-Instanz "ja" ist.

Wenn X NP-komplett ist und ein deterministischer Polynomialzeit-Algorithmus existiert, der alle Instanzen von X korrekt lösen kann (0% falsch-positiv, 0% falsch-negativ), dann kann jedes Problem in NP in deterministisch-polynomialer Zeit gelöst werden (durch Reduktion auf X).

Bisher hat noch niemand einen solchen deterministischen Polynomialzeit-Algorithmus entwickelt, aber auch noch niemand bewiesen, dass es ihn nicht gibt (es gibt eine Million Dollar für denjenigen, der beides schafft: das ist der P = NP-Problem ). Das bedeutet nicht, dass man eine bestimmte Instanz eines NP-kompletten (oder NP-schweren) Problems nicht lösen kann. Es bedeutet nur, dass man keine Lösung finden kann, die zuverlässig für alle Fälle eines Problems funktioniert, so wie man eine Liste von ganzen Zahlen zuverlässig sortieren kann. Es ist durchaus möglich, einen Algorithmus zu entwickeln, der für alle praktischen Fälle eines NP-schweren Problems sehr gut geeignet ist.

Answer 5

NP-Complete ist eine Klasse von Problemen.

Die Klasse P besteht aus jenen Problemen, die lösbar sind in Polynomzeit . Sie könnten zum Beispiel in O(n) gelöst werden k ) für eine gewisse Konstante k, wobei n ist die Größe der Eingabe. Einfach ausgedrückt, können Sie ein Programm schreiben, das in vernünftig Zeit.

Die Klasse NP besteht aus solchen Problemen, die nachprüfbar in polynomieller Zeit. Das heißt, wenn wir eine potenzielle Lösung erhalten, können wir in polynomialer Zeit prüfen, ob die gegebene Lösung korrekt ist.

Einige Beispiele sind die Boolesche Satisfiabilität (oder SAT ) oder das Hamilton-Zyklus-Problem. Es gibt viele Probleme, von denen bekannt ist, dass sie zur Klasse NP gehören.

NP-Complete bedeutet, das Problem ist mindestens so schwer wie jedes andere Problem in NP.

Es ist wichtig für die Informatik, weil bewiesen wurde, dass jedes Problem in NP umgewandelt in ein anderes NP-komplettes Problem. Das bedeutet, dass eine Lösung für ein beliebiges NP-komplettes Problem eine Lösung für alle NP-Probleme ist.

Viele Algorithmen im Bereich der Sicherheit beruhen auf der Tatsache, dass es für NP-schwere Probleme keine bekannten Lösungen gibt. Es hätte definitiv erhebliche Auswirkungen auf die Informatik, wenn eine Lösung gefunden würde.