Ist in ?

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? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

Ist in ? $AC^0/poly \cap NP$ $P$

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:

Gibt es einen Kandidaten für ein natürliches Problem in ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity 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

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Kaveh

@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

wobei

ein sehr schnell wachsenden Funktion; zweitens ist das Gegenbeispiel nicht nur in

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$ hat aber Schaltkreise der Größe 1, da die Funktion an allen Eingängen der Größe

für alle

konstant ist ! Diese beiden Gründe könnten bedeuten, dass dies nicht die richtige Frage ist.

n

$n$

n

$n$

Kaveh

@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

@Kaveh: Die Klasse YP ("Yoda Polynomial-Time") wird in Scotts Artikel "The Learnability of Quantum States" [quant-ph / 0608142]

Alessandro Cosentino

Antworten:

Hier ist eine Vereinfachung von Ryans Antwort. Nehmen wir an, dass . Definiere die Sprache . Die Annahme , übersetzt . Auch trivial . $\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Yuval Filmus
quelle

Schöne Antwort Yuval!

Dai Le

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

unär geschrieben?

| x |

$|x|$

x

$x$

Vincent

@Vincent Hier ist

eher ein String als eine ganze Zahl und

ist seine Länge.

x

$x$

| x |

$|x|$

Yuval Filmus

Ja, das ist es, was mich verwirrt. Wenn

ist die Länge eines Strings, dann

ist eine ganze Zahl, wie kann sie also ein Element von

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Vincent

Antwort auf deine erste Frage: Scheint unwahrscheinlich.

Theorem: Wenn dann . $NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

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

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

Betrachten wir nun die Sprache

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

ist eindeutig in , da Siefür jedes nur fest codieren können, ob in ist. $L$ $AC^0/poly$ $1^n$ $L$ $n$

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

Aber aus den gleichen Beobachtungen, wenn , dann ist , weil es bedeutet, dass Sie einen -Zeitalgorithmus haben, um jede Instanz von Succinct 3SAT der Länge zu bestimmen . $L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

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

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 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 das Problem durch einen linearen Entscheidungsbaum mit einer Tiefe kleiner als 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 wir möglicherweise einen völlig anderen Algorithmus (Entscheidungsbaum). $n$ $1$ $n$ $n^5$ $n$

Verweise:

Friedhelm Meyer auf der Heide, " Ein polynomischer linearer Suchalgorithmus für das n-dimensionale Rucksackproblem ", 1984

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

$n$

Kaveh

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

$2$

Kaveh

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 :-)

2^{n}

$2^n$

Stasys

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

. Dies ist jedoch eines der Ergebnisse.

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

Stasys

@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