Ist in ?

31

Ich dachte, ich würde diese Frage teilen, da sie für andere Benutzer hier interessant sein könnte.

Nehmen wir an, dass eine Funktion, die zu einer einheitlichen Klasse gehört (wie ), auch zu einer kleinen ungleichmäßigen Klasse gehört (wie , dh ungleichmäßige ), bedeutet, dass die Funktion zu einer kleineren einheitlichen Klasse gehört ( wie )? Wenn die Antwort auf diese Frage positiv ist, welche ist die kleinste einheitliche Komplexitätsklasse, die ? Wenn negativ, können wir ein interessantes natürliches Gegenbeispiel finden?A C 0 / P o l y A C 0 P N P A C 0 / P o l yNPAC0/polyAC0PNPAC0/poly

Ist in ?PAC0/polyNPP

Hinweis: Ein Freund hat meine Frage bereits teilweise offline beantwortet. Ich werde seine Antwort hinzufügen, wenn er sie nicht selbst hinzufügt.

Die Frage ist mein zweiter Versuch, die folgende informelle Frage zu formalisieren:

Kann uns die Uneinheitlichkeit bei der Berechnung natürlicher einheitlicher Probleme helfen?


Verbunden:

Kaveh
quelle
@Kaveh: Vielleicht wäre es eine interessante Frage, nach einem natürlichen Problem in P / Poly und NP zu fragen, aber nicht in P. (Oder vielleicht ist das zu einfach?)
Robin Kothari
@Robin: das scheint interessant, aber ich bin mir nicht sicher , dass es einfacher wäre , ein natürliches Problem in finden . NPP/polyP
Kaveh
1
@all: Ich muss ein bisschen mehr über diese Frage und die Antworten nachdenken. Es scheint eine sehr natürliche Frage zu sein. Aber ich fühle mich unwohl über die Antworten: Erstens können wir die Annahme schwächen durch Ersetzen mit N T i m e ( f ) D T i m e ( f ) wobei f ein sehr schnell wachsenden Funktion; zweitens ist das Gegenbeispiel nicht nur in A C 0 / p o l yNEXPEXPNTime(f)DTime(f)fAC0/polyhat aber Schaltkreise der Größe 1, da die Funktion an allen Eingängen der Größe für alle n konstant ist ! Diese beiden Gründe könnten bedeuten, dass dies nicht die richtige Frage ist. nn
Kaveh
2
@Kaveh: Vielleicht möchten Sie sich die Klasse YP ansehen, die von Scott Aaronson definiert wurde. Es ist wie P / Poly, aber der "Rat" ist nicht vertrauenswürdig. Mit anderen Worten, es ist wie bei der NP-Schnittmenge von coNP, aber der Zeuge kann nur von der Eingangslänge abhängen. YP ist in P / Poly und ist eine einheitliche Klasse. Vielleicht ist ein Problem in YP, aber nicht in P ein Beispiel für das gesuchte Problem. Es wäre natürlich, einheitlich, nicht in P, in P / Poly und möglicherweise nicht trivial, da der Hinweis von der Schaltung überprüft werden muss.
Robin Kothari
2
@Kaveh: Die Klasse YP ("Yoda Polynomial-Time") wird in Scotts Artikel "The Learnability of Quantum States" [quant-ph / 0608142]
Alessandro Cosentino

Antworten:

30

Hier ist eine Vereinfachung von Ryans Antwort. Nehmen wir an, dass . Definiere die Sprache L = { x : | x | Λ } . Die Annahme , & Lgr; N E E übersetzt L N P P . Auch trivial L A C 0 / p o l y .ΛNEEL={x:|x|Λ}ΛNEELNPPLAC0/poly

Yuval Filmus
quelle
1
Schöne Antwort Yuval!
Dai Le
1
Im Wesentlichen wird dieselbe Transformation in Buch 1974 verwendet, um zu zeigen, dass E ≠ NE genau dann ist, wenn NP ∖ P eine Zählsprache enthält.
Tsuyoshi Ito
Nur um sicher zu gehen: Verstehe ich das richtig ist die Länge von x unär geschrieben? |x|x
Vincent
@Vincent Hier ist eher ein String als eine ganze Zahl und | x | ist seine Länge. x|x|
Yuval Filmus
Ja, das ist es, was mich verwirrt. Wenn ist die Länge eines Strings, dann | x | ist eine ganze Zahl, wie kann sie also ein Element von Λ sein ? |x||x|Λ
Vincent
32

Antwort auf deine erste Frage: Scheint unwahrscheinlich.

Theorem: Wenn dann N E X P = E X P .NPAC0/polyPNEXP=EXP

Definieren Sie bei einer Schaltung , die ein Bit ausgibt, die Dekomprimierung von C als die Bitfolge, die durch Auswertung von C an allen möglichen Eingängen erhalten wird. Das heißt, die Dekompression ist C ( 0 n ) C ( 0 n - 1 1 ) C ( 0 n - 2 10 ) C ( 1 n ) .CCC(0n)C(0n11)C(0n210)C(1n)

Definieren Sie das Succinct 3SAT-Problem wie folgt: Codiert die Dekomprimierung bei einer Schaltung der Größe n eine erfüllbare Boolesche Formel? CnEs ist allgemein bekannt, dass prägnante 3SAT vollständig sind.NEXP

Betrachten wir nun die Sprache

{ 1 n | Diebinär geschriebeneGanzzahl n ist eine Ja-Instanz von Succinct 3SAT}.L=1n|n

ist eindeutig in A C 0 / p o l y , da Siefür jedes n nur fest codieren können, ob 1 n in L ist.LAC0/poly1nLn

ist auch in N P : Diein Binärschrift geschriebeneGanzzahl n hat eine Länge von etwa log n , so dass die Dekomprimierung dieser Schaltung eine Länge von nicht mehr als O ( n ) hat . Die befriedigende Zuordnung hat also höchstens die Länge O ( n ) .LNPnlognO(n)O(n)

Aber aus den gleichen Beobachtungen, wenn , dann ist N E X P = E X P , weil es bedeutet, dass Sie einen O ( n c ) -Zeitalgorithmus haben, um jede Instanz von Succinct 3SAT der Länge log n zu bestimmen .LPNEXP=EXPO(nc)logn

Ihre zweite Frage ist weit offen (und offen).

Ryan Williams
quelle
Warum musst du ein komplettes Problem haben?
Yuval Filmus
Dachte, es machte das Argument leichter zu folgen.
Ryan Williams
Danke Ryan für deine nette Antwort und die Erklärung. Ich denke, es würde Ihnen nichts ausmachen, wenn ich Yuvals Antwort akzeptiere, obwohl Sie die erste Person waren, die einen Beitrag geschrieben hat.
Kaveh
11

Auf die Frage von Kaveh: "Kann Ungleichmäßigkeit uns bei der Berechnung von natürlichen Gleichmäßigkeitsproblemen helfen?"

Ich denke, die Antwort lautet manchmal "Ja". Betrachten Sie beispielsweise das Subset-Sum-Problem: Entscheiden Sie bei einer Folge von positiven reellen Zahlen, ob eine Teilmenge von ihnen bis zu 1 summiert . Dies ist ein NP-hartes Problem, auch wenn es auf positive ganze Zahlen (Knapsack) beschränkt ist. Friedhelm Meyer auf der Heide (1984) hat jedoch gezeigt, dass für jedes n das Problem durch einen linearen Entscheidungsbaum mit einer Tiefe kleiner als n 5 gelöst werden kann . In einem solchen Baum haben Tests die Form: Ist eine lineare Kombination von Eingabevariablen, die einen bestimmten Schwellenwert überschreitet. Uneinheitlichkeit ist hier wichtig: Für jedes n haben wir möglicherweise einen völlig anderen Algorithmus (Entscheidungsbaum).n1nn5n

Verweise:

Stasys
quelle
Vielen Dank. Interessantes Ergebnis, aber wenn ich mir einen polynomialen linearen Suchalgorithmus für das n-dimensionale Rucksackproblem anschaue , kommt es mir ein wenig betrügerisch vor. Die Größe des ungleichmäßigen Programms ist exponentiell, nur die Tiefe ist polynomiell. Dies entspricht der Betrachtung des gesamten Berechnungsbaums eines NP-Algorithmus für Eingaben der Größe (dies entspricht Schaltkreisen mit polynomieller Tiefenexponentialgröße). n
Kaveh
1
Mit einem ähnlichen Argument können wir sagen, dass jedes Problem in konstanter Zeit lösbar ist , da die Tabelle der Antworten durch einen CNF ausgedrückt werden kann. Mir gefällt die Konstruktion von Ryan und Yuval besser, weil sie zeigt, dass das Problem zwar in der einheitlichen Einstellung kompliziert ist, aber für jede Eingabegröße sehr einfach zu lösen ist. 2
Kaveh
1
Kaveh, Sie haben Recht: Hier interessiert uns die Zeit (= Tiefe), nicht der Raum (= Protokoll der Netzwerkgröße). Beachten Sie jedoch, dass ein trivialer Algorithmus für Subset-Sum eine Zeit (Tiefe) von , um alle Teilmengen einer bestimmten Eingabezeichenfolge zu testen. Ich dachte auch, Sie fragen nach natürlichen Kandidaten, nicht nur zur Trennung :-)2n
Stasys
1
Natürlich hat das Subset-Sum-Problem einen trivialen, nicht deterministischen Algorithmus: Errate einfach eine Subset-Summe von . Wir sprechen aber von deterministischen Algorithmen. Und das von Mayer auf der Heide ist deterministisch. Übrigens freue ich mich auch nicht sehr über sein Ergebnis. Hätte er dies für die gezeigte Größe (nicht nur für depth = Zeit), würden wir bereits N P P / p o l y . Dies ist jedoch eines der Ergebnisse. 1NPP/poly
Stasys
4
@Kaveh: Aber NP selbst ist ein großer OP von P. Die "Zeitversion" von P vs. NP lautet: Können wir diesen großen OP durch einen deterministischen algebraischen Entscheidungsbaum mit polynomieller Tiefe (mit P auf den Blättern) ersetzen ? Denken Sie daran, dass die einfache Tiefe für Subset-Sum 2 ^ n (nicht n) ist. Dopkin und Lipton (1978) zeigten, dass die Tiefe n ^ 2/2 notwendig ist, und es wurde allgemein angenommen, dass dies für jedes k auf n ^ k verbessert werden kann. Mayer auf der Heide widerlegte diesen Glauben: k = 5 ist genug. Uneinheitlichkeit KANN also helfen, wenn wir an Tiefe (Zeit) interessiert sind.
Stasys