Ich versuche diese Klassifikationen zu verstehen und warum sie existieren. Ist mein Verständnis richtig? Wenn nicht, was dann?

1. P ist die Polynomkomplexität oder für eine nicht negative reelle Zahl , wie z. B. usw. Wenn ein Problem zu P gehört, gibt es mindestens einen Algorithmus, der es in der Polynomzeit von Grund auf lösen kann. Zum Beispiel kann ich immer herausfinden, ob eine Ganzzahl eine Primzahl ist, indem ich bei jedem Schritt eine Schleife durchführe und überprüfe, ob die Teilung erfolgt .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP ist nicht deterministische Polynomkomplexität. Ich weiß nicht genau, was es bedeutet, nicht deterministisch zu sein. Ich denke, es bedeutet, dass es einfach ist, in Polynomzeit zu verifizieren, aber es kann sein, dass es sich um eine Polynomzeit handelt, die von Grund auf gelöst werden kann, wenn wir die Antwort nicht bereits kannten. Da es kann in polynomieller Zeit lösbar sein, sind alle P Probleme auch Probleme NP. Die ganzzahlige Faktorisierung wird als Beispiel für NP angeführt, aber ich verstehe nicht, warum es nicht P ist, da die Versuchsfaktorisierung O(sqrt(n))Zeit braucht .

3. NP-Complete verstehe ich überhaupt nicht, aber das Travelling Salesman Problem ist ein Beispiel dafür. Meiner Meinung nach könnte das TSP-Problem jedoch nur NP sein, da es einer Prüfung bedarf, um den richtigen Weg zu finden.O(2n n2) time to solve, but O(n)

4. Ich nehme an, NP-Hard steckt voller Unbekannter. Schwer zu überprüfen, schwer zu lösen.

Sie haben grundsätzlich Recht mit P und NP, aber nicht mit NP-hard und NP-complete.

Für den Anfang sind hier die äußerst präzisen Definitionen der vier fraglichen Komplexitätsklassen:

• P ist die Klasse von Entscheidungsproblemen, die in der Polynomzeit von einer deterministischen Turingmaschine gelöst werden können.

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

• NP-hart ist die Klasse von Entscheidungsproblemen, auf die alle Probleme in NP durch eine deterministische Turing-Maschine in polynomialer Zeit reduziert werden können.

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

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

Der Teil, den Sie wahrscheinlich am wenigsten kennen oder durch den Sie verwirrt sind, ist der Begriff einer "Polynomzeitverkürzung" von Problem X zu Problem Y. Eine Verkürzung von X zu Y ist einfach ein Algorithmus A, der X durch Verwendung einiger löst anderer Algorithmus B, der das Problem Y löst. Diese Reduktion wird als "Polynomzeitreduktion" bezeichnet, wenn alle Teile von A außer B eine Polynomzeitkomplexität haben. Ein triviales Beispiel: Das Problem, das kleinste Element in einem Array zu finden, lässt sich zeitlich konstant auf das Sortierproblem reduzieren, da Sie das Array sortieren und dann das erste Element des sortierten Arrays zurückgeben können.

Eine Sache, die an der NP-harten Definition leicht zu übersehen ist, ist, dass die Reduktion von NP-Problemen zu NP-harten Problemen geht, aber nicht unbedingt umgekehrt . Dies bedeutet, dass NP-harte Probleme möglicherweise in NP oder in einer viel höheren Komplexitätsklasse vorliegen (wie Sie aus dem Euler-Diagramm ersehen können), oder dass es sich nicht einmal um entscheidbare Probleme handelt. Deshalb sagen die Leute oft etwas wie "NP-schwer bedeutet mindestens so schwer wie NP", wenn sie versuchen, dieses Zeug informell zu erklären.

Das Stopp-Problem ist ein gutes Beispiel für ein NP-hartes Problem, das eindeutig nicht in NP vorkommt, wie Wikipedia erklärt :

Es ist leicht zu beweisen, dass das Stopp-Problem NP-schwer, aber nicht NP-vollständig ist. Zum Beispiel kann das Problem der booleschen Erfüllbarkeit auf das Problem des Anhaltens reduziert werden, indem es in die Beschreibung einer Turing-Maschine umgewandelt wird, die alle Wahrheitswertzuweisungen versucht, und wenn sie eine findet, die die angehaltene Formel erfüllt, wird sie in eine Endlosschleife umgewandelt. Es ist auch leicht zu erkennen, dass das Stopp-Problem nicht in NP vorliegt, da alle Probleme in NP in einer begrenzten Anzahl von Operationen entscheidbar sind, während das Stopp-Problem im Allgemeinen nicht entscheidbar ist.

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

Für die Zwecke von Komplexitätsklassen nist das die Länge der Eingabe. Wenn Sie also eine ganze Zahl faktorisieren möchten k, nist dies nicht knur log kdie Anzahl der Bits (oder was auch immer), die zum Aufschreiben der Zahl erforderlich sind. Die ganzzahlige Faktorisierung ist O(sqrt(k))also so, wie Sie sagen, aber genau das ist es .O(sqrt(2n))O(2(n/2))

Ich nehme an, NP-Hard steckt voller Unbekannter. Schwer zu überprüfen, schwer zu lösen.

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

NP-harte Probleme sind zumindest das schwierigste Problem in NP. Wir wissen, dass sie mindestens 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-Complete verstehe ich überhaupt nicht

NP-Complete bedeutet, dass ein Problem sowohl NP als auch NP-Hard ist. Dies bedeutet, dass wir eine Lösung schnell verifizieren können (NP), aber es ist mindestens so schwierig wie das schwierigste Problem in NP (NP-Hard).

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

Nichtdeterminismus ist eine alternative Definition von NP. Eine nicht deterministische Turing-Maschine kann sich jederzeit selbst duplizieren und jedes Duplikat einen anderen Ausführungspfad verwenden. Nach dieser Definition ist NP die Menge der Probleme, die in polynomialer Zeit von einem Computer gelöst werden können, als sich frei duplizieren können. Es stellt sich heraus, dass dies genau die gleichen Probleme sind, die in der Polynomzeit verifiziert werden können.

Das erste, was zu verstehen ist, ist, dass P und NP Sprachen klassifizieren , keine 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 wie der ASCII-Zeichensatz ein Alphabet. {} 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 Σ heißt ein Wort über Σ .

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

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

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

Sei Σ ein Alphabet. Der Satz Σ ^* enthält alle Wörter über Σ , einschließlich ε . Die Menge Σ ⁺ enthält alle Wörter über Σ mit Ausnahme von ε . Für n ∈ N ist Σ ⁿ die Menge von Wörtern der Länge n .

Für jedes Alphabet Σ , Σ ^* und Σ ⁺ sind unendlich abzählbaren Mengen . Für den ASCII - Zeichensatz Σ _ASCII , die reguläre Ausdrücke .*und .+bezeichnen Σ _ASCII ^* und Σ _ASCII ⁺ sind.

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

Lassen Σ ein Alphabet und seine L ⊆ Σ ^* . L heißt eine Sprache über Σ .

Für ein Alphabet Σ , die leere Menge und Σ ^* sind Trivial 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 Nicht-NaN-IEEE-754-Gleitkommawerten entspricht, ist eine endliche Sprache.

Sprachen können unendlich viele Wörter enthalten, aber jede Sprache ist zählbar. Der Satz von Saiten { 1, 2...} bezeichnet die ganzen Zahlen in Dezimalschreibweise ist eine unendliche Sprache über das Alphabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Die unendliche Menge von Strings { 2, 3, 5, 7, 11, 13, ...} bezeichnet die Primzahlen in Dezimalschreibweise ist eine echte Teilmenge davon. Die Sprache, die alle Wörter enthält, die mit dem regulären Ausdruck übereinstimmen, [+-]?\d+\.\d*([eE][+-]?\d+)?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 enthält (in irgendeiner Notation), da die Menge der reellen Zahlen nicht zählbar ist.

Lassen Σ ein Alphabet und seine L ⊆ Σ ^* . Eine Maschine D entscheiden , L , wenn für jede Eingabe w ∈ & Sigma; ^* es der berechneten Kennfunktion χ _L ( w ) in endlicher Zeit. Die charakteristische Funktion ist definiert als

χ L : Σ * → {0, 1}
     w   ↦ 1,   w ∈ L 
         0, sonst.

Eine solche Maschine ist ein sogenannter decider für L . Wir schreiben " D ( w ) = x " für "gegebenes w , D gibt x aus ".

Es gibt viele Maschinenmodelle. Das allgemeinste Modell, das heute in der Praxis eingesetzt wird, ist das Modell einer Turing-Maschine . 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 Folge von Rechenschritten durch. In jedem Schritt kann er 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ührt, wird von einem endlichen Automaten gesteuert.

Eine Direktzugriffsmaschine mit einer begrenzten Anzahl von Anweisungen und unbegrenztem Speicherplatz ist ein weiteres Maschinenmodell, das genauso leistungsstark ist wie das Turing-Maschinenmodell.

Für diese Diskussion werden wir uns nicht mit dem genauen Maschinenmodell, das wir verwenden, befassen, sondern es genügt zu sagen, dass die Maschine eine endliche deterministische Steuereinheit und unbegrenzten Speicher hat und eine Berechnung als 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. Hier ist nur eine kurze Auffrischung.

Sei f : N → eine Funktion. Das Set O ( f ) enthält alle Funktionen g : N → N , für die Konstanten existieren n ₀ ∈ N und c ∈ N , so daß für jedes n ∈ N mit n > n ₀ es wahr ist , daß 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 , der entscheidet , L und eine Konstante k ∈ N , so daß für jeden Eingang w , D stoppt nach höchstens T (| w |) Schritte für eine Funktion T ∈ O ( n ↦ n ^k ).

Da das Schreiben und Lesen von O ( n ↦ n ^k ) mathematisch korrekt ist, schreiben die meisten Menschen - um ehrlich zu sein, alle außer mir - in der Regel einfach O ( n ^k ).

Beachten Sie, dass die Grenze von der Länge von w abhängt . Daher ist das Argument für die Sprache der Primzahlen nur für Zahlen in Unaray-Codierungen korrekt , wobei für die Codierung w einer Zahl n die Länge der Codierung | gilt 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 eine andere Basis) codiert sind. (Trotz massiven Interesses konnten dies nur Manindra Agrawal, Neeraj Kayal und Nitin Saxena beweisen In einem preisgekrönten Artikel aus dem Jahr 2004 kann man sich also vorstellen, 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 einen String als Eingabe verwenden und einen Booleschen Wert zurückgeben, der angibt, ob der String ein Wort aus der jeweiligen Sprache ist, und beweisen, dass Ihre Funktion eine polynomielle Laufzeitkomplexität hat?

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

Lassen Σ ein Alphabet und seine L ⊆ Σ ^* . Eine Maschine V , die ein codiertes Tupel von zwei Worten nehmen w , c ∈ & Sigma; ^* und gibt 0 oder 1 nach einer endlichen Anzahl von Schritten ist ein Verifizierer für L , wenn sie folgende Eigenschaften aufweisen.

• Wenn ( w , c ) gegeben ist, gibt V nur dann 1 aus, wenn w ≤ L ist .
• Für jedes w ∈ L existiert ein c ∈ & Sigma; ^* derart , daß V ( w , c ) = 1.

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

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

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

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 und eine Konstante k ∈ N verifiziert, so dass V für jede Eingabe ( w , c ) nach höchstens T (| w |) Schritten für eine Funktion anhält T ∈ O ( n ↦ n ^k ).

Man beachte, dass die obige Definition impliziert, dass für jedes w ∈ L ein Zeuge c mit | existiert c | ≤ T (| w |). (Die Turingmaschine kann unmöglich mehr Symbole des Zeugen sehen.)

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

Die ganzzahlige Faktorisierung ist an sich keine Sprache. 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 hat . Nennen wir diese Sprache FAKTOR. Wenn Sie einen Algorithmus zur Entscheidung von FACTOR haben, können Sie eine vollständige Faktorisierung mit nur polynomialem Overhead berechnen, indem Sie eine rekursive binäre Suche für jeden Primfaktor durchführen.

Es ist leicht zu zeigen, dass FACTOR 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 sind. Dies alles kann in Polynomzeit erfolgen. (Denken Sie auch hier daran, dass die Länge der Codierung zählt und in n logarithmisch 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 bedeutenden Teil der heutigen Kryptographie zerstört.)

Für jede Sprache in NP gibt es einen Brute-Force-Algorithmus, der dies deterministisch entscheidet . Es wird lediglich eine umfassende Suche nach allen Zeugen durchgeführt. (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 eine Reduzierung 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 Sprachen über Σ . A ist Polynom-Many-one- reduzierbar auf B , wenn es eine Funktion existiert f : Σ ^* → Σ ^* mit den folgenden Eigenschaften.

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

In diesem Fall schreiben wir A ≤ _p B .

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.) Es sei weiterhin B die Sprache, die alle Matrizen mit einer Spur ungleich Null enthält. (Die Spur einer Matrix ist die Summe seiner Hauptdiagonalelemente) . Dann A ist Polynom-Zeitviel einer reduzierbare zu B . Um dies zu beweisen, müssen wir eine geeignete Transformationsfunktion f finden . In diesem Fall können wir setzen f die 3 zu berechnen ^rd Leistung der Adjazenzmatrix. Dies erfordert zwei Matrix-Matrix-Produkte, von denen jedes eine polynomielle Komplexität aufweist.

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

Wir werden dies jetzt auf NP anwenden .

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

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

Eine Sprache L ist genau dann NP- vollständig, 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. Zum Beispiel ist ( 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 ausgeführt wurde .

Sobald diese eine NP- vollständige Sprache bekannt war, war es relativ einfach, die NP- Vollständigkeit anderer Sprachen durch Reduktion nachzuweisen. Wenn die Sprache A bekannt sein NP -hard, dann zeigt , dass A ≤ _p B zeigt , dass B ist NP -hard auch (über die Transitivität von „≤ _p “). 1972 veröffentlichte Richard Karp eine Liste mit 21 Sprachen, die er als NP ausweisen konnte-vollständig durch (transitiven) Abbau von SAT. (Dies ist das einzige Papier in dieser Antwort, von dem ich eigentlich empfehle, dass Sie es 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- Vollständigkeit durch Reduktion funktioniert.)

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

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

Es ist zu beachten, dass der Einschluss NPC ⊂ NP auch für den Fall geeignet ist, dass P = NP ist . Um dies zu sehen, machen Sie sich klar, dass keine nicht-triviale Sprache auf eine triviale Sprache reduziert werden kann und es sowohl triviale Sprachen in P als auch nicht-triviale Sprachen in NP gibt . Dies ist jedoch ein (nicht sehr interessanter) Eckfall.

Nachtrag

Ihre Hauptverwirrung scheint darin zu liegen, dass Sie sich das „ n “ in „ O ( n ↦ f ( n ))“ als Interpretation der Eingabe eines Algorithmus vorgestellt 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 erzielt. Die größte derzeit bekannte Primzahl ist 2 ^{74 207 281} - 1. Diese Zahl ist so groß, dass ich Kopfschmerzen habe. Im folgenden Beispiel verwende ich eine kleinere Zahl: 2 ³¹ - 1 = 2 147 483 647. Das kann es auf verschiedene Arten codiert werden.

• durch seinen Mersenne-Exponenten als Dezimalzahl: 31(2 Bytes)
• als Dezimalzahl: 2147483647(10 Bytes)
• als unäre Zahl: 11111…11wo die …durch 2 ersetzt werden soll 147 483 640 mehr 1s (fast 2 GiB)

Alle diese Zeichenfolgen codieren dieselbe Nummer, und wenn Sie eine dieser Zeichenfolgen angeben, können Sie problemlos eine andere Codierung mit derselben Nummer erstellen. (Sie können die Dezimalcodierung bei Bedarf durch Binär-, Oktal- oder Hexadezimalcodierung ersetzen. Sie ändert die Länge nur um einen konstanten Faktor.)

Der naive Algorithmus zum Testen der Primalität ist für unäre Codierungen nur ein Polynom. Der AKS-Primalitätstest ist ein Polynom für eine Dezimalzahl (oder eine beliebige andere Basis b ≥ 2). Der Lucas-Lehmer-Primalitätstest ist der bekannteste Algorithmus für Mersenne-Primzahlen M _p mit p einer ungeraden Primzahl, er ist jedoch 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 darüber im Klaren 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. Daher ist die Verwendung des Mersenne-Exponenten kein allgemeines Kodierungsschema.)

In der theoretischen Kryptographie wird vielen Algorithmen formal eine völlig nutzlose Folge von k 1 s als erster Parameter übergeben. Der Algorithmus betrachtet diesen Parameter nie, ermöglicht jedoch, dass er formal in k polynomisch ist. Dies ist der Sicherheitsparameter, der zum Optimieren der Sicherheit der Prozedur verwendet wird.

Bei einigen Problemen, bei denen die Entscheidungssprache bei der binären Codierung NP- vollständig ist, ist die Entscheidungssprache nicht mehr NP- vollständig, wenn die Codierung von eingebetteten Zahlen auf unär umgeschaltet wird. Die Entscheidungssprachen für andere Probleme bleiben auch dann NP- vollständig. Letztere werden als stark NP- vollständig bezeichnet . Das bekannteste Beispiel ist das Verpacken von Behältern .

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 von Mersenne-Primzahlen haben wir drei Codierungen gesehen, von denen jede logarithmisch stärker komprimiert ist als ihre Vorgängerin.

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

Das liegt daran, dass Sprachklassen wie P und NP für Sprachen definiert sind , nicht für Probleme .

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

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

NP-Problem: Probleme, die in Polynomzeit verifiziert werden können. Zum Beispiel: Reisender Verkäufer, Schaltungsentwurf. NP-Probleme ähneln Rätseln (wie Sudoku). Wenn wir eine korrekte Lösung für das Problem gefunden haben, können wir unsere Lösung sehr schnell überprüfen, aber wenn wir tatsächlich versuchen, sie zu lösen, kann es nur eine Ewigkeit dauern.

Nun fragt P vs NP tatsächlich, ob ein Problem, dessen Lösung schnell auf Richtigkeit überprüft werden kann, immer schnell gelöst werden kann. Schreiben Sie also mathematisch: Ist NP eine Teilmenge von P oder nicht?

Kommen wir nun zu NP complete 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 es eine davon, den besten Zug im Schach zu wählen.

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

Ich hoffe, dass dies eine unscharfe Kontur ergibt.