Sie haben grundsätzlich Recht mit P und NP, aber nicht mit NP-hart und NP-vollständig.

Für den Anfang hier die überprägnanten Definitionen der vier fraglichen Komplexitätsklassen:

• P ist die Klasse von Entscheidungsproblemen, die in polynomieller Zeit von einer deterministischen Turing-Maschine gelöst werden können.

• NP ist die Klasse von Entscheidungsproblemen, die in Polynomzeit von einer nicht deterministischen Turing-Maschine gelöst werden können. Entsprechend ist es die Klasse von Problemen, die verifiziert werden kann in Polynomzeit durch eine deterministische Turing-Maschine.

• NP-hart ist die Klasse von Entscheidungsproblemen, für die alle Probleme in NP sein können durch eine deterministische Turing-Maschine auf Polynomzeit reduziert.

• NP-vollständig ist der Schnittpunkt von NP-hart und NP. Entsprechend ist NP-vollständig die Klasse von Entscheidungsproblemen in NP, auf die alle anderen Probleme in NP durch eine deterministische Turing-Maschine in Polynomzeit reduziert werden können.

Und hier „sa Euler-Diagramm aus Wikipedia , das die Beziehungen zwischen diesen vier Klassen zeigt (unter der Annahme, dass P nicht gleich NP ist):

Der Teil, von dem ich annehme, dass Sie ihn am wenigsten kennen oder verwirren ist der Begriff einer „Polynomzeitreduktion“ von Problem X zu Problem Y. Eine Reduktion von X zu Y ist einfach ein Algorithmus A, der X löst, indem ein anderer Algorithmus B verwendet wird, der Problem Y löst. Diese Reduktion wird als “ Polynomzeitreduktion „wenn alle Teile von A außer B eine Polynomzeitkomplexität haben. Als triviales Beispiel ist das Problem, das kleinste Element in einem Array zu finden, zeitlich konstant auf das Sortierproblem reduzierbar, da Sie das Array sortieren und dann das erste Element des sortierten Arrays zurückgeben können.

Eins Was bei der NP-harten Definition leicht zu übersehen ist, ist, dass die Reduzierung von NP-Problemen zu NP-harten Problemen geht, aber nicht unbedingt umgekehrt . Dies bedeutet, dass NP-harte Probleme sein können in NP oder in einer viel höheren Komplexitätsklasse (wie Sie aus dem Euler-Diagramm sehen können), oder sie sind möglicherweise nicht einmal entscheidbare Probleme.Deshalb sagen die Leute oft etwas wie „NP-hart bedeutet mindestens so hart wie NP“, wenn sie versuchen, dieses Zeug informell zu erklären.

Das Problem des Anhaltens ist ein gutes Beispiel für ein NP-hartes Problem, das „s eindeutig nicht in NP, wie Wikipedia erklärt :

Es ist einfach zu beweisen, dass das Stoppproblem NP-hart, aber nicht NP-vollständig ist. Zum Beispiel kann das boolesche Erfüllbarkeitsproblem auf das Stoppproblem reduziert werden, indem es in die Beschreibung einer Turing-Maschine umgewandelt wird, die alle Wahrheitswertzuweisungen versucht, und wenn sie eine findet, die die Formel erfüllt, wird sie angehalten und geht ansonsten in eine Endlosschleife. Es ist auch leicht zu erkennen, dass das Stoppproblem nicht in NP liegt, da alle Probleme in NP in einer endlichen Anzahl von Operationen entscheidbar sind, während das Stoppproblem im Allgemeinen unentscheidbar ist.

Kommentare

• @Nakano Intuitiv ist ‚ sa “ Reduktion “ in dem Sinne, dass ein Problem zu einem Teilproblem eines anderen Problems gemacht wird. Die Tatsache, dass einige dieser Reduzierungen die Komplexität erhöhen, anstatt sie durch eine schlechte Auswahl des “ -Unterproblems “ zu verringern, bedeutet einfach, dass Sie diese Reduzierungen niemals verwenden würden in jedem realen Code. Um ehrlich zu sein, scheint mir NP-hard eine seltsame und nicht besonders interessante Klasse zu sein. Es kann fruchtbarer sein, es zu ignorieren und sich NP-complete als die Menge von NP-Problemen vorzustellen, auf die sich alle anderen NP-Probleme reduzieren.
• @Nakano stackoverflow.com/questions/12637582/… Ich glaube, die kurze Antwort lautet: Wenn Leute davon sprechen, dass die ganzzahlige Faktorisierung NP ist, ‚ spricht normalerweise von wirklich großen Ganzzahlen, für die Sie im Allgemeinen Ihre Big-O-Beweise mit n als “ der Anzahl der Bits ausführen, die die Ganzzahl im Speicher “ anstelle von “ die Anzahl der Ganzzahlen, die Sie an die Funktion “ übergeben haben.
• @Nakano: In der Big-O-Notation ist die n ein Maß für die Größe der Eingabe (Anzahl der Elemente, Bytes, Ziffern usw.), nicht für den Wert der Eingabe.
• @Nakano Die kurze Antwort lautet, dass es Ihnen ‚ gut geht, und deshalb, wenn Sie Zeit co mplexity analaysis Sie müssen immer angeben, was n bedeutet . Die Behauptung, dass n “ die Größe der Eingabe “ ist, ist lediglich eine kurze Zusammenfassung dessen, wie wir normalerweise n definieren. ‚ ist nicht Teil der strengen Definitionen der Big-O-Notation oder der Zeitkomplexität. Ich glaube, Sie sagen zu Recht, dass die ganzzahlige Faktorisierung O (sqrt (n)) ist, wenn n der Wert der Eingabe ist. Es kommt einfach so vor, dass die Komplexitätsergebnisse, bei denen n Größe bedeutet, in der Praxis normalerweise viel nützlicher sind als diejenigen, bei denen n Wert bedeutet.
• @Nakano It ‚ Beachten Sie auch, dass Sie technisch auch die zeitliche Komplexität Ihrer primitiven Operationen definieren müssen (Addition, Multitplikation, Lesen aus dem Speicher, Schreiben in den Speicher, Vergleichen von zwei Zahlen). Die meiste Zeit nehmen wir entweder an, dass alle diese Grundelemente konstant sind, oder wir zählen nur eine Art von Operation (z. B. zählen wir für Sortieralgorithmen traditionell die Vergleiche). Ich vermute, dass die Ergebnisse für die Ganzzahlfaktorisierung ‚ nicht davon ausgehen, dass alle diese Operationen zeitkonstant sind, wie wir es normalerweise tun, sonst würde die Größe der Zahl nicht ‚ spielt keine große Rolle.

Die Ganzzahlfaktorisierung wird als Beispiel für NP angeführt, aber ich verstehe nicht, warum es persönlich nicht P ist, da die Versuchsfaktorisierung O (sqrt (n)) Zeit benötigt.

Für die Zwecke von Komplexitätsklassen ist n die Länge der Eingabe. Wenn Sie also die Ganzzahl k faktorisieren möchten, ist n nicht k, sondern log k, die Anzahl der Bits (oder was auch immer), die zum Aufschreiben der Anzahl erforderlich sind. Die Ganzzahlfaktorisierung ist also O(sqrt(k)), wie Sie sagen, aber dies ist O(sqrt(2n)), was O(2(n/2)) ist.

NP-Hard ist vermutlich nur voller Unbekannter. Schwer zu überprüfen, schwer zu lösen.

Nein. Bei NP-Hard geht es lediglich darum, wie schwer ein Problem zu lösen ist.

NP-Hard-Probleme sind mindestens so schwer wie das schwierigste Problem in NP. Wir wissen, dass sie zumindest so schwer sind, denn wenn wir einen Polynom-Zeit-Algorithmus für ein NP-Hard-Problem hätten, könnten wir diesen Algorithmus an jedes Problem in NP anpassen.

NP-vollständig Ich verstehe überhaupt nicht

NP- Vollständig bedeutet, dass ein Problem sowohl NP als auch NP-schwer ist. Dies bedeutet, dass wir eine Lösung schnell überprüfen können (NP), aber es ist mindestens so schwer wie das schwierigste Problem in NP (NP-schwer).

Ich weiß nicht genau, was es bedeutet, nicht deterministisch zu sein.

Non -Determinismus ist eine alternative Definition von NP. Eine nicht deterministische Turingmaschine kann sich jederzeit effektiv selbst duplizieren und jedes Duplikat einen anderen Ausführungspfad nehmen lassen. Nach dieser Definition ist NP die Menge der Probleme, die in Polynomzeit von einem Computer gelöst werden können, als sich selbst frei duplizieren können. Es stellt sich heraus, dass dies genau die gleichen Probleme sind, die in der Polynomzeit überprüft werden können.

Kommentare

• Es ist also möglich für $ O ( n ^ k) $ Zeitalgorithmen als NP-Probleme?
• k ist eine konstante reelle Zahl? Ja. Alle P-Probleme sind auch NP-Probleme. Natürlich kann alles, was Sie in der Polynomzeit lösen können, auch in der Polynomzeit überprüft werden.
• Wie wird hier tatsächlich Länge / Größe definiert? Zum Beispiel könnte ich einfach $ n $ in eine große Basis schreiben und deren Länge beim Schreiben verringern. Was ist mit Problemen, bei denen ‚ nicht explizit Ganzzahlen behandelt, sondern Diagramme mit $ V $ -Scheitelpunkten und $ E $ -Kanten usw.
• @Nakano Eine große Basis würde ‚ es nicht ändern, da es sich nur um eine konstante Faktordifferenz handelt. ‚ würde also kein Polynom gegen Nicht-Polynom bewirken. Wenn Sie die Zahl jedoch unärisch schreiben würden, würde sich dies ändern.
• @Nakano, hmm … Ich würde es nicht wagen, die Komplexität zu erklären, ‚ Klassen zu einem fünfjährigen. : P

Das erste, was zu verstehen ist, ist, dass P und NP klassifizieren Sprachen , nicht Probleme . Um zu verstehen, was dies bedeutet, benötigen wir zuerst einige andere Definitionen.

Ein Alphabet ist eine nicht leere endliche Menge von Symbolen.

{0 , 1} ist ein Alphabet, ebenso wie der ASCII-Zeichensatz. {} ist kein Alphabet, weil es leer ist. N (die ganzen Zahlen) ist kein Alphabet, weil es nicht endlich ist.

Lassen Sie Σ sei ein Alphabet. Eine geordnete Verkettung einer endlichen Anzahl von Symbolen aus Σ wird als Wort über Σ .

Die Zeichenfolge 101 ist ein Wort über dem Alphabet {0, 1}. Das leere Wort (oft geschrieben als ε ) ist ein Wort über einem beliebigen Alphabet. Die Zeichenfolge penguin ist ein Wort über dem Alphabet, das die ASCII-Zeichen enthält. Die Dezimalschreibweise der Zahl π ist kein Wort über dem Alphabet {., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, weil es nicht endlich ist.

Die Länge eines Wortes w , geschrieben als | w |, ist die Anzahl der Symbole darin.

Zum Beispiel | hello | = 5 und | ε | = 0. Für jedes Wort w gilt | w | ∈ N und daher endlich.

Lassen Sie Σ sei ein Alphabet. Die Menge Σ ^＊ enthält alle Wörter über Σ , einschließlich ε . Die Menge Σ ⁺ enthält alle Wörter über Σ , ausgenommen ε . Für n ∈ N ist Σ ⁿ ist die Menge der Wörter der Länge n .

Für jedes Alphabet Σ , Σ ^＊ und Σ ⁺ sind unendlich zählbare Mengen .Für den ASCII-Zeichensatz Σ _ASCII sind die regulären Ausdrücke .* und .+ bezeichnet Σ _ASCII ^＊ und Σ _ASCII ⁺ .

{0, 1} ⁷ ist der Satz von 7-Bit-ASCII-Codes {0000000, 0000001, …, 1111111}. {0, 1} ³² ist die Menge von 32-Bit-Ganzzahlwerten.

Sei Σ ein Alphabet und L ⊆ Σ ^＊ . L heißt Sprache über Σ .

Für ein Alphabet Σ ist die leere Menge und Σ ^＊ sind triviale Sprachen über Σ . Ersteres wird oft als leere Sprache bezeichnet. Die leere Sprache {} und die Sprache, die nur das leere Wort { ε } enthält, sind unterschiedlich.

Die Teilmenge von {0, 1} ³² , die Gleitkommawerten nach Nicht-NaN IEEE 754 entsprechen, ist eine endliche Sprache.

Sprachen können unendlich viele Wörter haben, aber jede Sprache ist zählbar. Die Menge der Zeichenfolgen {1, 2,…}, die die Ganzzahlen in Dezimalschreibweise bezeichnen, ist eine unendliche Sprache über dem Alphabet {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. Die unendliche Menge von Zeichenfolgen {2, 3, 5, 7, 11, 13,…}, die die Primzahlen in Dezimalschreibweise bezeichnen, sind eine geeignete Teilmenge davon. Die Sprache, die alle Wörter enthält, die mit dem regulären Ausdruck [+-]?\d+\.\d*([eE][+-]?\d+)? übereinstimmen, ist eine Sprache über dem ASCII-Zeichensatz (der eine Teilmenge der gültigen Gleitkommaausdrücke gemäß der Programmiersprache C bezeichnet).

Es gibt keine Sprache, die alle reellen Zahlen enthält (in einer beliebigen Notation), da die Menge der reellen Zahlen nicht zählbar ist.

Lassen Sie Σ ist ein Alphabet und L ⊆ Σ ^＊ . Eine Maschine D entscheidet L , wenn für jede Eingabe w ∈ Σ ^＊ berechnet die charakteristische Funktion χ _L ( w ) in endlicher Zeit. Die charakteristische Funktion ist definiert als

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Eine solche Maschine wird als Entscheider für L . Wir schreiben „ D ( w ) = x “ für „gegebenes w , D gibt x aus.

Es gibt viele Maschinenmodelle. Das allgemeinste, das heute in der Praxis verwendet wird, ist das Modell einer Turingmaschine . Eine Turing-Maschine verfügt über unbegrenzten linearen Speicher, der in Zellen zusammengefasst ist. Jede Zelle kann zu jedem Zeitpunkt genau ein Symbol eines Alphabets enthalten. Die Turing-Maschine führt ihre Berechnung als eine Folge von Berechnungsschritten durch. In jedem Schritt kann es eine Zelle lesen, möglicherweise ihren Wert überschreiben und den Lese- / Schreibkopf um eine Position nach links oder rechts bewegen. Welche Aktion die Maschine ausführen wird, wird von einem Automaten mit endlichem Zustand gesteuert.

Eine Maschine mit wahlfreiem Zugriff mit endlichen Anweisungen und unbegrenztem Speicher ist ein weiteres Maschinenmodell, das genauso leistungsfähig ist wie das Modell der Turing-Maschine.

Für diese Diskussion werden wir uns nicht mit dem genauen Maschinenmodell beschäftigen, das wir verwenden, sondern es genügt zu sagen, dass die Maschine eine endliche deterministische Steuereinheit, unbegrenzten Speicher hat und eine Berechnung als eine Folge von Schritten durchführt das kann gezählt werden.

Da Sie es in Ihrer Frage verwendet haben, gehe ich davon aus, dass Sie bereits mit der „big-O“ -Notation Hier ist also nur eine kurze Auffrischung.

Lassen Sie f : N → sei eine Funktion.Die Menge O ( f ) enthält alle Funktionen g : N → N für die Konstanten n ₀ ∈ N und c ∈ N , so dass für jedes n ∈ N mit n > n ₀ ist wahr, dass g ( n ) ≤ c f ( n ).

Jetzt sind wir bereit, uns der eigentlichen Frage zu nähern.

Die Klasse P enthält alle Sprachen L , für die es eine Turing-Maschine D gibt, die L entscheidet und eine Konstante k ∈ N , so dass für jede Eingabe w D hält nach höchstens T (| w |) Schritten für eine Funktion T O ( n ↦ n ^k ).

Seit O ( n ↦ n ^k ) ist zwar mathematisch korrekt, aber unpraktisch zu schreiben und zu lesen. Die meisten Leute – um ehrlich zu sein, alle außer mir – schreiben normalerweise einfach O ( n ^k ).

Beachten Sie, dass die Grenze von der Länge von abhängt w . Daher ist das Argument, das Sie für die Sprache der Primzahlen vorbringen, nur für Zahlen in unaray-Codierungen korrekt, wobei für die Codierung w von eine Zahl n , die Länge der Codierung | w | ist proportional zu n . Niemand würde jemals eine solche Codierung in der Praxis verwenden. Mit einem fortgeschritteneren Algorithmus als dem einfachen Ausprobieren aller möglichen Faktoren kann jedoch gezeigt werden, dass die Sprache der Primzahlen in P bleibt, wenn die Eingaben binär (oder auf einer anderen Basis) codiert sind. (Trotz massiven Interesses konnte dies nur von Manindra Agrawal, Neeraj Kayal und Nitin Saxena in einer preisgekrönten Veröffentlichung im Jahr 2004 bewiesen werden Der Algorithmus ist nicht sehr einfach.)

Die trivialen Sprachen {} und Σ ^＊ und die nicht triviale Sprache { ε } sind offensichtlich in P (für jedes Alphabet) Σ ). Können Sie Funktionen in Ihrer bevorzugten Programmiersprache schreiben, die eine Zeichenfolge als Eingabe verwenden und einen Booleschen Wert zurückgeben, der angibt, ob die Zeichenfolge für jede dieser Funktionen ein Wort aus der Sprache ist, und nachweisen, dass Ihre Funktion eine polynomielle Laufzeitkomplexität aufweist?

Jede reguläre Sprache (eine Sprache, die durch einen regulären Ausdruck beschrieben wird) ist in P .

Sei Σ ein Alphabet und L ⊆ Σ ^＊ . Eine Maschine V , die ein codiertes Tupel aus zwei Wörtern w , c ∈ verwendet Σ ^＊ und gibt 0 oder 1 aus, nachdem eine endliche Anzahl von Schritten ein Verifizierer für L , wenn es die folgenden Eigenschaften hat.

• Gegeben ( w , c ), V gibt 1 nur aus, wenn w ∈ L .
• Für jedes w ∈ L gibt es existiert ein c ∈ Σ ^＊ , so dass V ( w , c ) = 1.

Das c in der obigen Definition wird als Zeuge (oder Zertifikat ) bezeichnet.

Ein Prüfer darf falsche Negative für den falschen Zeugen angeben, selbst wenn w tatsächlich in L ist. Es ist jedoch nicht gestattet, falsch positive Ergebnisse zu erzielen. Es ist auch erforderlich, dass für jedes Wort in der Sprache mindestens ein Zeuge vorhanden ist.

Für die Sprache COMPOSITE enthält diese die Dezimalcodierungen aller Ganzzahlen, die nicht prim sind Ein Zeuge könnte eine Faktorisierung sein. Beispielsweise ist (659, 709) ein Zeuge für 467231 ∈ COMPOSITE. Sie können dies auf einem Blatt Papier leicht überprüfen, ohne dass der Zeuge angegeben wurde. Der Nachweis, dass 467231 keine Primzahl ist, wäre ohne Verwendung eines Computers schwierig.

Wir haben nichts darüber gesagt, wie ein geeigneter Zeuge sein kann gefunden. Dies ist der nicht deterministische Teil.

Die Klasse NP enthält alle Sprachen L , für die es eine Turing-Maschine gibt V , das L und eine Konstante k ∈ N überprüft, so dass für jeden Eingabe ( w , c ), V hält nach höchstens T (| w i) an > |) Schritte für eine Funktion T ∈ O ( n ↦ n ^k ).

Beachten Sie, dass die obige Definition impliziert, dass für jedes w ∈ L ein Zeuge c mit existiert | c | ≤ T (| w |). (Die Turing-Maschine kann möglicherweise nicht mehr Symbole des Zeugen anzeigen.)

NP ist eine Obermenge von P (warum?). Es ist nicht bekannt, ob es Sprachen gibt, die sich in NP , aber nicht in P befinden.

Die Ganzzahlfaktorisierung ist an sich keine Sprache. Wir können jedoch eine Sprache erstellen, die das damit verbundene Entscheidungsproblem darstellt. Das heißt, eine Sprache, die alle Tupel ( n , m ) enthält, so dass n einen Faktor d mit hat d ≤ m . Nennen wir diese Sprache FAKTOR. Wenn Sie über einen Algorithmus zur Entscheidung von FACTOR verfügen, können Sie eine vollständige Faktorisierung mit nur Polynom-Overhead berechnen, indem Sie eine rekursive binäre Suche für jeden Primfaktor durchführen.

Es ist leicht zu zeigen, dass FACTOR in NP. Ein geeigneter Zeuge wäre einfach der Faktor d selbst, und der Prüfer müsste lediglich überprüfen, ob d ≤ m und n mod d = 0. All dies kann in Polynomzeit erfolgen. (Denken Sie erneut daran, dass die Länge der Codierung zählt und logarithmisch in n ist.)

Wenn Sie zeigen können, dass FACTOR auch in P enthalten ist, können Sie sicher sein, dass Sie viele coole Auszeichnungen erhalten. (Und Sie haben einen erheblichen Teil der heutigen Kryptographie zerstört.)

Für jede Sprache in NP gibt es einen Brute-Force-Algorithmus, der entscheidet es deterministisch. Es führt einfach eine erschöpfende Suche über alle Zeugen durch. (Beachten Sie, dass die maximale Länge eines Zeugen durch ein Polynom begrenzt ist.) Ihr Algorithmus zur Entscheidung von PRIMES war also tatsächlich ein Brute-Force-Algorithmus zur Entscheidung von COMPOSITE.

Um Ihre letzte Frage zu beantworten, müssen wir Reduktion einführen. Reduktionen sind ein sehr leistungsfähiges Konzept der theoretischen Informatik. Das Reduzieren eines Problems auf ein anderes bedeutet im Grunde, ein Problem durch Lösen eines anderen zu lösen Problem.

Sei Σ ein Alphabet und A und B sind Sprachen über Σ . A ist polynomial-time many-one reducible auf B , wenn eine Funktion f existiert: Σ ^＊ → Σ ^＊ mit den folgenden Eigenschaften.

• w ∈ A   ⇔   f ( w ) ∈ B   für alle w ∈ Σ ^＊ .
• Die Funktion f kann von einer Turing-Maschine für jede Eingabe berechnet werden w in mehreren Schritten, die durch ein Polynom in | w | begrenzt sind.

In diesem Fall schreiben wir A ≤ _p B .

Für Beispiel: A ist die Sprache, die alle Diagramme (als Adjazenzmatrix codiert) enthält, die ein Dreieck enthalten. (Ein Dreieck ist ein Zyklus der Länge 3.) Sei weiter B die Sprache, die alle Matrizen mit einer Spur ungleich Null enthält. (Die Spur einer Matrix ist die Summe ihrer Hauptdiagonalelemente.) Dann ist A eine auf B reduzierbare Polynomzeit von vielen Eins. Um dies zu beweisen, müssen wir eine geeignete Transformationsfunktion f finden. In diesem Fall können wir f einstellen, um die 3. Potenz der Adjazenzmatrix zu berechnen. Dies erfordert zwei Matrix-Matrix-Produkte, von denen jedes eine Polynomkomplexität aufweist.

Es ist trivial wahr, dass L ≤ _p L . (Können Sie es formal beweisen?)

Wir werden dies jetzt auf NP anwenden.

Eine Sprache L ist NP -hard genau dann, wenn L „≤ _p L für jede Sprache L “ ∈ NP .

Eine NP -harte Sprache kann oder kann nicht in NP selbst sein.

Eine Sprache L ist NP -complete genau dann, wenn

• L ∈ NP und
• L ist NP hart.

Die bekannteste NP -vollständige Sprache ist SAT. Es enthält alle booleschen Formeln, die erfüllt werden können. Beispiel: ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Ein gültiger Zeuge ist { a = 1, b = 0}. Die Formel ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Wie würden Sie das beweisen?)

Es ist nicht schwer zu zeigen, dass SAT ∈ NP . Die NP -Härte von SAT zu zeigen, ist eine Arbeit, die 1971 von Stephen Cook durchgeführt wurde.

Sobald diese eine NP -vollständige Sprache bekannt war, war es relativ einfach, die NP -Vollständigkeit anderer Sprachen durch Reduktion zu zeigen. Wenn bekannt ist, dass die Sprache A NP hart ist, wird angezeigt, dass A ≤ _p B zeigt, dass B auch NP hart ist (über die Transitivität von “ _p ”). 1972 veröffentlichte Richard Karp eine Liste von 21 Sprachen, von denen er zeigen konnte, dass sie durch (transitive) Reduktion von SAT NP vollständig waren. (Dies ist das einzige Papier in dieser Antwort, das Sie unbedingt lesen sollten. Im Gegensatz zu den anderen ist es nicht schwer zu verstehen und gibt eine sehr gute Vorstellung davon, wie der Nachweis der NP -Komplettität durch Reduktion funktioniert. )

Zum Schluss noch eine kurze Zusammenfassung. Wir werden die Symbole NPH und NPC verwenden, um die Klassen von NP -hard und NP -vollständigen Sprachen zu bezeichnen jeweils.

• P ⊆ NP
• NPC ⊂ NP und NPC ⊂ NPH , tatsächlich NPC = NP ∩ NPH per Definition
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

Beachten Sie, dass der Einschluss NPC ⊂ NP auch dann richtig ist, wenn P. = NP Um dies zu sehen, machen Sie sich klar, dass keine nicht triviale Sprache auf eine triviale reduziert werden kann und es auch in P triviale Sprachen gibt als nicht triviale Sprachen in NP . Thi s ist jedoch ein (nicht sehr interessanter) Eckfall.

Nachtrag

Ihre Hauptverwirrungsquelle scheint zu sein, dass Sie an das „ n ”in“ O ( n ↦ f ( n i) >)) ”Als Interpretation der Eingabe eines Algorithmus, wenn sie sich tatsächlich auf die Länge der Eingabe bezieht. Dies ist eine wichtige Unterscheidung, da dies bedeutet, dass die asymptotische Komplexität eines Algorithmus von der für die Eingabe verwendeten Codierung abhängt.

Diese Woche wurde ein neuer Datensatz für die größte bekannte Mersenne prime wurde erreicht. Die größte derzeit bekannte Primzahl ist 2 74   207   281 – 1. Diese Zahl ist so groß dass es mir Kopfschmerzen bereitet, so dass ich im folgenden Beispiel ein kleineres verwenden werde: 2 ³¹ – 1 = 2   147   483   647. Es kann auf verschiedene Arten codiert werden.

• durch seinen Mersenne-Exponenten als Dezimalzahl: 31 (2 Bytes)
• als Dezimalzahl: 2147483647 (10 Bytes)
• als unär Nummer: 11111…11 wobei die … durch 2   147   483   640 weitere 1 s (fast 2 GiB)

Alle diese Zeichenfolgen codieren dieselbe Nummer, und wenn Sie eine dieser Zeichenfolgen verwenden, können Sie problemlos jede andere Codierung derselben Nummer erstellen. (Sie können die Dezimalcodierung durch Binär-, Oktal- oder Hexadeci-Codierung ersetzen mal wenn du willst Die Länge wird nur um einen konstanten Faktor geändert.)

Der naive Algorithmus zum Testen der Primalität ist nur für unäre Codierungen polynomisch. Der AKS-Primalitätstest ist ein Polynom für die Dezimalzahl (oder eine andere Basis b ≥ 2 ).Der Lucas-Lehmer-Primalitätstest ist der bekannteste Algorithmus für Mersenne-Primzahlen M _p mit p eine ungerade Primzahl, aber es ist immer noch exponentiell in der Länge der binären Codierung des Mersenne-Exponenten p (Polynom in p ) ).

Wenn wir über die Komplexität eines Algorithmus sprechen möchten, ist es sehr wichtig, dass wir uns sehr klar darüber sind, welche Darstellung wir verwenden. Im Allgemeinen kann man davon ausgehen, dass die effizienteste Codierung verwendet wird. Das heißt, binär für ganze Zahlen. (Beachten Sie, dass nicht jede Primzahl eine Mersenne-Primzahl ist, sodass die Verwendung des Mersenne-Exponenten kein allgemeines Codierungsschema ist.)

In der theoretischen Kryptographie wird vielen Algorithmen formal eine völlig nutzlose Zeichenfolge von k 1 s als erster Parameter. Der Algorithmus betrachtet diesen Parameter nie, erlaubt jedoch, dass er in k , dem Sicherheitsparameter , formal polynomisch ist / a> wird verwendet, um die Sicherheit der Prozedur zu optimieren.

Bei einigen Problemen, bei denen die Entscheidungssprache in der Binärcodierung NP vollständig ist, ist die Entscheidungssprache nicht mehr NP -vollständig, wenn die Codierung eingebetteter Nummern auf unär geschaltet ist. Die Entscheidungssprachen für andere Probleme bleiben auch dann NP vollständig. Letztere werden als stark NP -vollständig bezeichnet. Das bekannteste Beispiel ist bin packing .

Es ist auch (und vielleicht noch interessanter) zu sehen, wie Die Komplexität eines Algorithmus ändert sich, wenn die Eingabe komprimiert ist. Für das Beispiel der Mersenne-Primzahlen haben wir drei Codierungen gesehen, von denen jede logarithmisch stärker komprimiert ist als ihre Vorgängerin.

1983 Hana Galperin und Avi Wigderson hat ein interessantes Papier über die Komplexität gängiger Graphalgorithmen geschrieben, wenn die Eingabecodierung des Graphen logarithmisch komprimiert wird. Für diese Eingaben wird die Sprache der Graphen, die ein Dreieck von oben enthalten (wo es eindeutig in P war), plötzlich NP vollständig.

Und das „s, weil Sprachklassen wie P und NP für Sprachen definiert sind, nicht für Probleme .

Kommentare

• Diese Antwort ist wahrscheinlich nicht hilfreich für das Verständnis des Fragestellers. Lesen Sie die anderen Antworten und sehen Sie, womit Nanako zu kämpfen hat. Denken Sie das? Antwort hilft ihm / ihr?
• Diese Antwort hilft OP möglicherweise nicht, hilft aber sicherlich anderen Lesern (ich selbst eingeschlossen).
• sehr hilfreiche Antwort! sollte erwägen, die mathematischen Symbole nicht richtig zu korrigieren angezeigt.

Ich werde versuchen, Ihnen weniger informelle Definitionen dafür zu geben.

P-Probleme: Probleme, die in Polynomzeit gelöst werden können. Enthält Probleme, die effizient lösbar sind.

NP-Problem: Probleme, die in Polyno verifiziert werden können Zeit. Zum Beispiel: Reisender Verkäufer, Schaltungsentwurf. NP-Probleme sind wie Rätsel (wie Sudoku). Wenn wir eine korrekte Lösung für das Problem gefunden haben, können wir unsere Lösung sehr schnell überprüfen. Wenn wir jedoch tatsächlich versuchen, sie zu lösen, kann dies ewig dauern.

Nun fragt P vs NP tatsächlich, ob ein Problem vorliegt, dessen Lösung schnell sein kann überprüft, um korrekt zu sein, dann gibt es immer einen schnellen Weg, um es zu lösen. Mathematisch ausgedrückt: Ist NP eine Teilmenge von P oder nicht?

Kommen wir nun zu NP zurück: Dies sind die wirklich schwierigen Probleme der NP-Probleme. Wenn es also einen schnelleren Weg gibt, NP vollständig zu lösen, wird NP vollständig zu P und NP-Probleme fallen in P zusammen. NP schwer: Probleme, die nicht einmal in der Polynomzeit überprüft werden können, sind np schwer. Zum Beispiel ist die Auswahl des besten Schachzugs eine davon.

Wenn etwas unklar bleibt, schauen Sie sich dieses Video an: https://www.youtube.com/watch?v=YX40hbAHx3s

Ich hoffe, dass dies zu einer verschwommenen Kontur führt.