Warum werden Gleichheiten zwischen Komplexitätsklassen nach oben und nicht nach unten übersetzt?

25

, ich verstehe, dass der Auffülltrick es uns ermöglicht, Komplexitätsklassen nach oben zu übersetzen - zum Beispiel . Das Auffüllen funktioniert, indem die Eingabe "aufgeblasen" und die Konvertierung ausgeführt wird (etwa von in P ). Dies ergibt einen "magischen" Algorithmus, den Sie für die aufgefüllte Eingabe ausführen können. Obwohl dies technisch sinnvoll ist, kann ich keine gute Vorstellung davon bekommen, wie dies funktioniert. Was genau ist hier los? Gibt es eine einfache Analogie für die Polsterung?N PP=NPEXP=NEXPNPP

Kann ein vernünftiger Grund angegeben werden, warum dies der Fall ist?

gabgoh
quelle
11
Ich möchte darauf hinweisen, dass nicht alle Ergebnisse der Komplexitätsklasse nach oben gehen. Wenn Sie beispielsweise , würde dies bedeuten . Im Allgemeinen steigen die Einbrüche, während die Trennungen sinken. P N PEXPNEXPPNP
Robin Kothari
tatsächlich. Tatsächlich scheint dies eine gute Möglichkeit zu sein, um darüber nachzudenken, da Trennungen intuitiver sind als Zusammenbrüche.
Gabgoh
2
@Robin, @gabgoh: Sogar einige Einbrüche gehen nach unten, aber nicht durch Auffüllen von Argumenten. Siehe zum Beispiel arxiv.org/abs/cs/9910008 .
Joshua Grochow

Antworten:

30

Ich denke, der beste Weg, um sich ein Bild von diesem Thema zu machen, besteht darin, sich die vollständigen Probleme für exponentielle Zeitklassen vorzustellen. Zum Beispiel sind die vollständigen Probleme für NE die standardmäßigen NP-vollständigen Probleme für kurz beschreibbare Eingaben. Ist der Graph 3-färbbar, wenn zum Beispiel eine Schaltung gegeben ist, die die Adjazenzmatrix eines Graphen beschreibt? Dann wird das Problem, ob E = NE ist, gleichbedeutend damit, ob NP-Probleme in Polynomzeit auf den prägnant beschreibbaren Eingaben lösbar sind, z. B. auf Eingaben mit geringer effektiver Kolmogorov-Komplexität. Dies ist offensichtlich nicht stärker, als ob sie für alle Eingaben lösbar sind. Je größer die Zeitgrenze ist, desto kleiner ist die Kolmogorov-Komplexität der relevanten Eingaben, so dass Kollaps für größere Zeitgrenzen tatsächlich Algorithmen sind, die auf kleineren Teilmengen von Eingaben arbeiten.

Russell Impagliazzo

Russell Impagliazzo
quelle
14

OK, Ihr Ziel ist es also zu zeigen, dass basierend auf C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) ]CLASS1[g(f(n))]=CLASS2[h(f(n))]CLASS1[g(n)]=CLASS2[h(n)](Wir geben nicht genau an, was diese Klassen sind, wir wissen nur, dass sie irgendwie mit der Eingabegröße parametrisiert sind). Wir haben eine Sprache , die von einem Algorithmus A bestimmt wird . Nun bilden wir eine Sprache L ', indem wir jedes Wort in x L auffüllen , so dass seine Länge jetzt f ( n ) ist und wir sehen, dass es in C L A S S 1 [ g] enthalten istLCLASS1[g(f(n))]ALxLf(n) (unser neuer Algorithmus A ' ignoriert im Grunde genommen nur die hinzugefügten Nullen und führt A für die reale, kurze Eingabe aus).CLASS1[g(n)]AA

Was wir tun, ist: Wir nehmen eine Sprache aus der größeren Klasse und füllen sie auf, damit sie durch einen schwächeren Algorithmus gelöst werden kann, der uns in die kleinere Klasse einschließt "echte Arbeit", um wie zuvor zu tun, aber es hat seine Einschränkungen (in Abhängigkeit von der Länge der Eingabe) durch die Erweiterung der Eingabe aufgehoben.

Nun weiß man , dass und damit L 'C L A S S 2 [ h ( n ) ] (von einigem Algorithmus entschieden , B ' ). Wir möchten von hier aus zu L C L A S S 2 [ h ( f ( n ) ) ]LCLASS1[g(n)]LCLASS2[h(n)]BLCLASS2[h(f(n))]. Dies ist jedoch unkompliziert - der Algorithmus entscheidet, dass L die Eingabe entsprechend auffüllt, und führt B ' für die aufgefüllte Eingabe aus.BLB

Dieser Schritt kann wie folgt zusammengefasst werden: Wir möchten in der größeren, einfallsreicheren Klasse entscheiden. Mit unseren zusätzlichen Ressourcen füllen wir die Eingabe auf und führen den Algorithmus aus, der die aufgefüllte Sprache bestimmtL .

Natürlich handelt es sich hierbei um einige technische Details (z. B. müssen wir sicherstellen, dass die Auffüllung in den Klassen, die wir betrachten, implementiert werden kann), aber ich ignoriere sie einfach, um die allgemeine Intuition zu vermitteln.

Karolina Sołtys
quelle
13

Ich sehe die Auffüllargumente in Bezug auf die Kompaktheit der Darstellung. Stellen Sie sich zwei Übersetzer-Turing-Maschinen vor: sprengt Instanzen und C komprimiert sie erneut.BC

Das Auffüllargument arbeitet mit , indem es B mit der deterministischen Version des TM für die Sprache in der unteren nicht deterministischen Klasse zusammensetzt. Die Ausgaben von B bilden zusammen eine Sprache, die nicht kompakt dargestellt wird, so dass dies "einfacher" wird.BBB

Es ist nicht möglich, die Idee mit anders anzuwenden , da nur einige der Sprachen in der easy-Klasse durch das Sprengen von Sprachen in der hard-Klasse generiert werden.C

András Salamon
quelle
5

Um es intuitiver zu machen, schauen wir uns an, was abstrakter vor sich geht!

Wir haben zwei Transformationen, eine für Eingänge und einen für problems.I beide durch bezeichnen wird , es aus dem Zusammenhang klar sein wird , wenn es das erste ist , und wenn es die zweite.pad

Diese beiden Transformationen haben die folgende Eigenschaft:

I. für alle Probleme , für alle Eingänge x & egr ; & Sgr; * :AΣxΣ

wenn x A ,pad(x)pad(A)xA

II. wenn in ist E X P ( N E X P ) ist , dann p a d ( A ) ist in P ( N P ).AEXPNEXPpad(A)PNP

III. die Transformation für Eingaben ist in der Komplexitätsklasse ,EXP

Es ist klar, dass die Transformationen für das Auffüllen diese Eigenschaften haben.

Der Grund, warum wir nicht wissen, wie wir dasselbe in umgekehrter Richtung tun sollen, ist, dass wir keine Transformationen wie das Auffüllen in umgekehrter Richtung haben (wenn wir mit P und N E X P mit N tauschen) P ). Die Frage ist also warum?EXPPNEXPNP

Ich habe kein formelles Argument, warum es im Moment keine solchen Transformationen gibt, aber intuitiv ist das, was András Salamon sagte, richtig. Es ist einfach, die Größe von Eingaben zu erhöhen, aber es ist nicht klar, wie sie komprimiert werden können.

Ein anderer Weg, dies zu verstehen, ist, wie folgt darüber nachzudenken. Es sei angenommen , dass , und wir wollen ein lösen N E X P = N T i m e ( 2 n O ( 1 ) ) Problem. Wir sind eine Eingabe gegeben x der Länge n , wir denken , es als eine Eingabe der Länge N = 2 n OP=NPNEXP=NTime(2nO(1))xn :N=2nO(1)

NEXP(n)=NTime(2nO(1))=NTime(N)NP(N)P(N)=Time(NO(1))=Time(2nO(1))=EXP(n)

Kaveh
quelle
1
Das letztere Argument, das ich als eine Art Argument der "Transformation von Variablen" betrachte, ist mir eingefallen. Ich verstehe jedoch nicht, warum man nicht einfach daran "denken" kann, wenn man eine Eingabe von say, wodurch man es herunterübersetzt. Ich denke nicht, dass dies funktioniert, obwohl die beiden anderen Ansätze es sinnvoll erscheinen lassen, einem NP-Algorithmus mehr Ressourcen zu geben, und in Bezug auf Komprimierung und Auffüllen. N=log(n)
Gabgoh
1
Ein dritter Weg, um darüber nachzudenken, ist, das Gegenteil zu betrachten. Ich habe diesen Ansatz nicht bis zum bitteren Ende verfolgt, aber wenn ich einen guten Einblick bekomme, poste ich ihn als Antwort auf mich.
Gabgoh
1
N=2nO(1)nNNnN=log(n)
Kaveh
1
nN=log(n)PNP) mit unärer Kodierung wird in EXP (NEXP) mit binärer Kodierung.
Kaveh
1
Ich denke, mein Problem liegt in der Phrase "Denken an". Ich kann nicht verstehen, was es bedeutet, eine kleinere Eingabe als eine größere Eingabe zu betrachten und was dies in der Realität bewirkt. Mir ist klar, dass Sie nicht daran denken könnenN=lOG(n)Aus dem Grund, den Sie angeben, was eine Wiederholung des Auffüllungsarguments ist, keine klare Analogie, nehme ich an. Wenn wir Variablen ändern, denken wir immer an Variablen in Bezug auf andere Variablen, aber im Gegensatz zu echten Variablen ist es irgendwie "inkompressibel". Um nicht zu sagen, es ist eine schlechte Antwort, aber es hilft mir persönlich nicht viel.
gabgoh