Der Versuch, P vs NP vs NP Complete vs NP Hard zu verstehen

Das erste, was zu verstehen ist, ist, dass P und NP Sprachen klassifizieren, keine Probleme. Um zu verstehen, was das bedeutet, brauchen wir zuerst einige andere Definitionen.

Ein Alphabet ist eine nicht leere endliche Menge von Symbolen.

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

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

Der String 101 ist ein Wort über dem Alphabet {01}. Das leere Wort (oft als ε geschrieben) ist ein Wort über jedem Alphabet. Die Zeichenfolge penguin ist ein Wort über dem Alphabet, das die ASCII-Zeichen enthält. Die Dezimalnotation der Zahl π ist kein Wort über dem Alphabet {.0123456789} weil es nicht endlich.

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, | w / ∈ N und daher endlich.

Σ sei ein Alphabet. Die Menge Σ＊ enthält alle Wörter über Σ, einschließlich ε. Die Menge Σ+ enthält alle Wörter über Σ, mit Ausnahme von ε. Für n ∈ N ist Σn die Menge der Wörter der Länge n.

Für jedes Alphabet Σ sind Σ＊ und Σ+ unendlich zählbare Mengen. Für den ASCII-Zeichensatz ΣASCII bezeichnen die regulären Ausdrücke .* und .+ ΣASCII＊ bzw. ΣASCII+.

{01}7 ist der Satz von 7-Bit-ASCII-Codes {00000000000001111111101}32 ist die Menge von 32-Bit-ganzzahligen Werten.

Sei Σ ein Alphabet und L ⊆ Σ＊. L wird eine Sprache über Σ genannt.

Für ein Alphabet Σ sind die leere Menge und Σ＊ 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 {01}32, die Nicht-NaN IEEE 754 Gleitkommawerten entspricht, ist eine endliche Sprache.

Sprachen können unendlich viele Wörter haben, aber jede Sprache ist zählbar. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. Die unendliche Menge von Strings {23571113, …} Die Primzahlen in Dezimalschreibweise bezeichnen, ist eine richtige Teilmenge davon. Die Sprache, die alle Wörter enthält, die mit dem regulären Ausdruck ?\d+\.\d*(?\d+)? übereinstimmen, ist eine Sprache über dem ASCII-Zeichensatz (bezeichnet eine Teilmenge der gültigen Gleitkommaausdrücke, wie sie in der Programmiersprache C definiert sind).

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

Sei Σ ein Alphabet und L ⊆ Σ＊. Eine Maschine D entscheidet L, wenn sie für jeden Eingang w ∈ Σ＊ die charakteristische Funktion xL(w) in endlicher Zeit berechnet. Die charakteristische Funktion ist definiert als

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

Eine solche Maschine wird als Entscheider für L bezeichnet.

Es gibt viele Maschinenmodelle. Das allgemeinste, das heute in der Praxis verwendet wird, ist das Modell einer Turing-Maschine. Eine Turing-Maschine hat unbegrenzten linearen Speicher, der in Zellen gruppiert ist. Jede Zelle kann zu jedem Zeitpunkt genau ein Symbol eines Alphabets enthalten. Die Turingmaschine führt ihre Berechnung als Folge von Rechenschritten durch. In jedem Schritt kann er eine Zelle lesen, ggf. ihren Wert überschreiben und den Schreib-/Lesekopf um eine Position nach links oder rechts verschieben. Welche Aktion die Maschine ausführen wird, wird von einem endlichen Zustandsautomaten gesteuert.

Eine Direktzugriffsmaschine mit einem endlichen Satz von Anweisungen und unbegrenztem Speicher ist ein weiteres Maschinenmodell, das so leistungsfähig ist wie das Turing-Maschinenmodell.

Um dieser Diskussion willen 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 hat, unbegrenzten Speicher und eine Berechnung als eine Folge von Schritten durchführt, die gezählt werden können.

Da Sie es in Ihrer Frage verwendet haben, gehe ich davon aus, dass Sie bereits mit der „Big-O“ -Notation vertraut sind.

Sei f: N → eine Funktion. Die Menge O(f) enthält alle Funktionen g: N → N, für die Konstanten n0 ∈ N und c ∈ N existieren, so dass für jedes n ∈ N mit n > n0 gilt, dass g(n) ≤ cf(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 Turingmaschine D gibt, die L entscheidet, und eine Konstante k ∈ N, so dass für jeden Eingang W D nach höchstens T(| w/) Schritten für eine Funktion T hal O(n ↦ nk) anhält.

Da O(n ↦ nk) zwar mathematisch korrekt, aber unbequem zu schreiben und zu lesen ist, schreiben die meisten Menschen – um ehrlich zu sein, alle außer mir – normalerweise einfach O(nk).Daher ist das Argument, das Sie für die Sprache der Primzahlen verwenden, nur für Zahlen in Unaray-Codierungen korrekt, wobei für die Codierung w einer Zahl n die Länge der Codierung |w| proportional zu n . Niemand würde jemals eine solche Codierung in der Praxis verwenden. Mit einem fortschrittlicheren 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 eine andere Basis) codiert sind. (Trotz des massiven Interesses konnte dies nur von Manindra Agrawal, Neeraj Kayal und Nitin Saxena in einem preisgekrönten Artikel im Jahr 2004 bewiesen werden, sodass Sie vermuten können, dass der Algorithmus nicht sehr einfach ist.)

Die Trivialsprachen {} und Σ＊ und die Nicht-Trivialsprache {ε} 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 beweisen, dass Ihre Funktion eine polynomische 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 ∈ Σ＊ nimmt und nach einer endlichen Anzahl von Schritten 0 oder 1 ausgibt, ist ein Verifikator für L, wenn sie die folgenden Eigenschaften aufweist.

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

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

Ein Verifizierer darf für den falschen Zeugen falsche Negative geben, auch wenn w tatsächlich in L ist. Es ist auch erforderlich, dass für jedes Wort in der Sprache mindestens ein Zeuge existiert.

Für die Sprachzusammensetzung, die die Dezimalkodierungen aller ganzen Zahlen enthält, die nicht Primzahlen sind, könnte ein Zeuge eine Faktorisierung sein. Beispiel: (659, 709) ist ein Zeuge für 467231 ∈ COMPOSITE. Sie können leicht überprüfen, dass auf einem Blatt Papier, während ohne den Zeugen gegeben, zu beweisen, dass 467231 nicht prime ist, wäre schwierig, ohne einen Computer zu verwenden.

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

Die Klasse NP enthält alle Sprachen L, für die es eine Turingmaschine V gibt, die L verifiziert, und eine Konstante k ∈ N, so dass für jede Eingabe (w, c) V nach höchstens T(| w/) Schritten für eine Funktion T hal O(n ↦ nk) anhält.

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

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

Ganzzahlige Faktorisierung ist keine Sprache an sich. Wir können jedoch eine Sprache konstruieren, 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 d ≤ m . Nennen wir diesen Sprachfaktor. Wenn Sie einen Algorithmus haben, um den FAKTOR zu bestimmen, kann er verwendet werden, um eine vollständige Faktorisierung mit nur Polynom-Overhead zu berechnen, indem eine rekursive binäre Suche für jeden Primfaktor durchgeführt wird.

Es ist leicht zu zeigen, dass der FAKTOR in NP ist. 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 noch einmal daran, dass die Länge der Codierung zählt und logarithmisch in n ist.)

Wenn Sie zeigen können, dass dieser FAKTOR auch in P ist, können Sie sicher sein, viele coole Auszeichnungen zu erhalten. (Und Sie haben einen bedeutenden Teil der heutigen Kryptographie gebrochen.)

Für jede Sprache in NP gibt es einen Brute-Force-Algorithmus, der sie deterministisch entscheidet. Es führt einfach eine erschöpfende Suche über alle Zeugen. (Beachten Sie, dass die maximale Länge eines Zeugen durch ein Polynom begrenzt ist.) Also, Ihr Algorithmus, um PRIMZAHLEN zu entscheiden, war eigentlich ein Brute-Force-Algorithmus, um COMPOSITE zu entscheiden.

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

Σ sei ein Alphabet und A und B seien Sprachen über Σ. A ist Polynomzeit viele-eins reduzierbar auf B, wenn es eine Funktion f: Σ＊ → Σ＊ mit den folgenden Eigenschaften gibt.

• w ∈ A ⇔ f(w) ∈ B für alle w ∈ Σ＊.
• Die Funktion f kann von einer Turingmaschine für jeden Eingang w in einer Anzahl von Schritten berechnet werden, die durch ein Polynom in |w| begrenzt sind.

In diesem Fall schreiben wir A ≤p B.

Zum Beispiel sei A die Sprache, die alle Graphen (codiert als Adjazenzmatrix) 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 diagonalen Hauptelemente. Um dies zu beweisen, müssen wir eine geeignete Transformationsfunktion f . In diesem Fall können wir f setzen, 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 wenden dies jetzt auf NP an.

Eine Sprache L ist genau dann NP-hart, wenn L‘ ≤p L für jede Sprache L‘ ∈ NP .

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

Eine Sprache L ist genau dann NP-vollständig, wenn

• L ∈ NP und
• L NP-hart ist.

Die bekannteste NP-vollständige Sprache ist SAT. Es enthält alle booleschen Formeln, die erfüllt werden können. Zum 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ürdest du das beweisen?)

Es ist nicht schwer zu zeigen, dass SAT ∈ NP. Die NP-Härte von SAT zu zeigen, ist etwas Arbeit, aber es wurde 1971 von Stephen Cook gemacht.

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 Sprache A NP-hart ist, zeigt die Darstellung von A ≤p B , dass auch B NP-hart ist (über die Transitivität von „≤p“). Im Jahr 1972 veröffentlichte Richard Karp eine Liste von 21 Sprachen, die er zeigen konnte, waren NP-komplett über (transitive) Reduktion von SAT. (Dies ist das einzige Papier in dieser Antwort, das ich Ihnen tatsächlich empfehlen sollte. Im Gegensatz zu den anderen ist es nicht schwer zu verstehen und gibt eine sehr gute Vorstellung davon, wie der Nachweis der NP-Vollständigkeit durch Reduktion funktioniert.)

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

• P &Teilmenge q; NP
• NPC &Teilmenge; NP und NPC &Teilmenge; NPH, eigentlich NPC = NP ∩ NPH per Definition
• (A ∈ NP) ∧ (B ∈ NPH) ⇒ A ≤p B

Beachten Sie, dass die Einbeziehung NPC &Teilmenge; NP ist auch in dem Fall richtig, dass P = NP . Um dies zu sehen, machen Sie sich klar, dass keine nicht-triviale Sprache auf eine triviale Sprache reduziert werden kann und es triviale Sprachen in P sowie nicht-triviale Sprachen in NP gibt. Dies ist jedoch ein (nicht sehr interessanter) Eckfall.Ihre primäre Quelle der Verwirrung scheint zu sein, dass Sie an das „n“ in „O (n ↦ f(n))“ als Interpretation der Eingabe eines Algorithmus gedacht haben, wenn es sich tatsächlich auf die Länge der Eingabe bezieht. Dies ist ein wichtiger Unterschied, da die asymptotische Komplexität eines Algorithmus von der für die Eingabe verwendeten Codierung abhängt.

Diese Woche wurde ein neuer Rekord für den größten bekannten Mersenne Prime erreicht. Die größte derzeit bekannte Primzahl ist 274 207 281 − 1. Diese Zahl ist so groß, dass sie mir Kopfschmerzen bereitet, daher verwende ich im folgenden Beispiel eine kleinere: 231 – 1 = 2 147 483 647. Es kann auf verschiedene Arten codiert werden.

• durch seinen Mersenne-Exponenten als Dezimalzahl: 31 (2 Byte)
• als Dezimalzahl: 2147483647 (10 Byte)
• als unäre Zahl: 11111…11 wobei die … ist durch 2 147 483 640 mehr zu ersetzen 1s (fast 2 GiB)

Alle diese Zeichenfolgen kodieren dieselbe Nummer, und bei jeder dieser Zeichen können wir problemlos jede andere Kodierung derselben Nummer erstellen. (Sie können die Dezimalcodierung durch binär, oktal oder hexadezimal ersetzen, wenn Sie möchten. Es ändert nur die Länge um einen konstanten Faktor.)

Der naive Algorithmus zum Testen der Primalität ist nur für unäre Kodierungen polynomisch. Der AKS-Primalitätstest ist Polynom für Dezimal (oder jede andere Basis b ≥ 2). Der Lucas-Lehmer-Primalitätstest ist der bekannteste Algorithmus für Mersenne-Primzahlen Mp 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 wollen, ist es sehr wichtig, dass wir sehr klar sind, welche Repräsentation 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, daher ist die Verwendung des Mersenne-Exponenten kein allgemeines Codierungsschema.)

In der theoretischen Kryptographie wird vielen Algorithmen formal eine völlig nutzlose Zeichenfolge von k 1s als erster Parameter übergeben. Der Algorithmus betrachtet diesen Parameter nie, aber er erlaubt ihm, formal ein Polynom in k zu sein, was der Sicherheitsparameter ist, der verwendet wird, um die Sicherheit der Prozedur abzustimmen.

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 Zahlen auf unär umgeschaltet wird. Die Entscheidungssprachen für andere Probleme bleiben auch dann NP-vollständig. Letztere werden stark NP-vollständig genannt. Das bekannteste Beispiel ist Bin Packing.

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

Im Jahr 1983 haben Hana Galperin und Avi Wigderson einen interessanten Artikel über die Komplexität gängiger Graphenalgorithmen geschrieben, wenn die Eingangscodierung 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 liegt daran, dass Sprachklassen wie P und NP für Sprachen definiert sind, nicht für Probleme.