Ist NPI in P / Poly enthalten?

Es wird vermutet, dass da die Umkehrung \ mathsf {PH} = \ Sigma_2 implizieren würde . Ladners Theorem besagt, dass wenn \ mathsf {P} \ ne \ mathsf {NP}, dann \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset . Der Beweis scheint jedoch nicht auf \ mathsf {P} / \ text {poly} zu verallgemeinern, sodass die Möglichkeit besteht, dass \ mathsf {NPI} \ subset \ mathsf {P} / \ text {poly} dh \ mathsf {NP} \ subset \ mathsf {NPC} \ cup \ mathsf {P} / \ text {poly} scheint offen zu sein.$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\mathsf{PH} = \Sigma_2$$\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$$\mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$$\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$

Angenommen, $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ (oder sogar, dass die Polynomhierarchie auf keiner Ebene zusammenbricht), lautet \ mathsf {NPI} \ subset \ mathsf {P} / \ text {poly}$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ als wahr oder falsch bekannt? Welche Beweise können dafür und dagegen erbracht werden?

Hier ist eine mögliche Alternative zu einem Auffüllargument, das auf Schönings Verallgemeinerung des Ladner-Theorems basiert. Um das Argument zu verstehen, müssen Sie Zugriff auf dieses Dokument haben (das leider für viele hinter einer Lohnwand steht):

Uwe Schöning. Ein einheitlicher Ansatz, um Diagonalsätze in Komplexitätsklassen zu erhalten. Theoretical Computer Science 18 (1): 95-103, 1982.

Wir wenden den Hauptsatz aus dieser Arbeit für und als Sprachen und und als Komplexitätsklassen wie folgt an:$A_1$$A_2$$\mathsf{C}_1$$\mathsf{C}_2$

• $A_1 = \varnothing$ (oder eine beliebige Sprache in )$\mathsf{P}$
• $A_2 = \text{SAT}$
• $\mathsf{C}_1 = \mathsf{NPC}$
• $\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

Der Klarheit halber wird der Beweis dass impliziert .$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Unter der Annahme, dass , haben wir und . Es ist klar, dass und unter endlichen Variationen geschlossen sind. Schönings Arbeit enthält einen Beweis, dass rekursiv darstellbar ist (die genaue Definition finden Sie in der Arbeit), und der schwierigste Teil des Arguments besteht darin, zu beweisen, dass rekursiv darstellbar ist.$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$A_1\not\in\mathsf{C}_1$$A_2\not\in\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$

Unter diesen Voraussetzungen impliziert der Satz, dass es eine Sprache gibt, die weder in noch in ; und , dass , ist Karp-reduzierbar auf und daher . Da sich in aber weder in noch in , folgt .$A$$\mathsf{C}_1$$\mathsf{C}_2$$A_1\in\mathsf{P}$$A$$A_2$$A\in\mathsf{NP}$$A$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP} \cap \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Es bleibt zu beweisen, dass rekursiv darstellbar ist. Grundsätzlich bedeutet dies, dass es eine explizite Beschreibung einer Folge deterministischer Turing-Maschinen die alle an allen Eingaben anhalten und so sind, dass . Wenn meine Argumentation fehlerhaft ist, ist sie wahrscheinlich hier, und wenn Sie dieses Ergebnis wirklich verwenden müssen, sollten Sie dies sorgfältig tun. Wie auch immer, durch Verzahnung aller nicht deterministischen Turing-Maschinen mit Polynomzeit (die deterministisch simuliert werden können, weil wir uns nicht um die Laufzeit jedes$\mathsf{NP} \cap \mathsf{P/poly}$$M_1, M_2, \ldots$$\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$$M_k$) und alle Polynome, die Obergrenzen für die Größe einer Booleschen Schaltkreisfamilie für eine bestimmte Sprache darstellen. Ich glaube, es ist nicht schwierig, eine Aufzählung zu erhalten, die funktioniert. Im Wesentlichen kann jedes testen, ob sein entsprechendes Polynom-Zeit-NTM mit einer Familie von Polynomgrößenschaltungen bis zu der Länge der Eingangszeichenfolge übereinstimmt, die es durch Durchsuchen aller möglichen Booleschen Schaltungen erhält. Wenn Übereinstimmung besteht, gibt wie der NTM aus, andernfalls lehnt er ab (und repräsentiert als Ergebnis eine endliche Sprache).$M_k$$M_k$

Die grundlegende Intuition hinter dem Argument (das in Schönings Ergebnis verborgen ist) ist, dass es niemals zwei "nette" Komplexitätsklassen (dh solche mit rekursiven Präsentationen) geben kann, die disjunkt sind und bündig aneinander sitzen. Die "Topologie" komplexer Klassen lässt dies nicht zu: Sie können eine Sprache immer korrekt zwischen den beiden Klassen konstruieren, indem Sie bei extrem langen Eingabelängen irgendwie zwischen beiden wechseln. Theorem zeigt dies für und , und Schönings Verallgemeinerung lässt Sie dasselbe für viele andere Klassen tun.$\mathsf{P}$$\mathsf{NPC}$

Ich möchte nur eine Version eines Auffüllarguments aufschreiben, wie in den Kommentaren beschrieben. Ich verstehe nicht, warum eine Lücke benötigt wird. Wir wollen zeigen, dass, wenn NP nicht in P / Poly enthalten ist, es ein NP-intermediäres Problem gibt, das nicht in P / Poly enthalten ist.

Es gibt eine unbegrenzte Funktion so dass SAT keine Schaltkreise mit einer Größe von weniger als , und daher gibt es eine Funktion , die unbegrenzt ist, zunimmt und . Es sei SAT 'die Sprache, die durch Auffüllen von SAT-Zeichenfolgen der Länge mit . Dann:$f$$n^{f(n)}$$g$$g(n)=o(f(n))$$n$$n^{g(n)}$

• SAT 'ist in NP (siehe unten!)
• SAT 'ist nicht in P / poly: Bei Schaltungen der Größe für SAT' erhalten wir Schaltungen der Größe für SAT, aber dies ist weniger als für einige .$n^k$$n^{g(n)k}$$n^{f(n)}$$n$
• Es gibt keine P / Poly-Reduktion von SAT zu SAT ': Nehmen wir an, dass es für SAT Schaltkreise der Größe , die SAT-Gatter erlauben. Pick groß genug , dass und lassen . Jedes SAT'-Gatter in hat höchstens Eingänge. Durch Entfernen der Auffülleingaben können wir die SAT-Gatter in auf ein SAT-Gatter mit weniger als Eingaben trimmen , die wir mit simulieren können - die resultierenden SAT-Gatter haben höchstens Eingänge. Wiederholen Sie dies und behandeln Sie von Hand. SAT würde Schaltkreise von ungefährer Größe haben$C_n$$n^k$$N$$g(\sqrt{N}) > 2k$$n>N$$C_n$$n^k$$C_n$$\sqrt{n}$$C_{\sqrt{n}}$$n^{k/2}$$C_N$$O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$ das für einige kleiner als .$n^{f(n)}$$n$

Bearbeiten:

Die Wahl von ist etwas fummelig. Wenn Sie gerne SAT 'in die Versprechen-Version von NP einfügen, ist dieses Bit nicht erforderlich.$g$

Definieren Sie als maximale Ganzzahl, sodass es für Länge Zeichenfolgen für SAT keine Schaltung der Größe . Definieren Sie mit einem Algorithmus, der für berechnet und nach der Zeit stoppt oder wenn , und den Boden der Quadratwurzel des höchsten in dieser Zeit gefundenen Werts zurückgibt . Also ist unbegrenzt und und können in der Zeit berechnet werden . Beachten Sie nun, dass die obigen Argumente nur darauf beruhen, dass SAT für unendlich viele keine Schaltkreise der Größe$f(n)$$n^{f(n)}$$n$$g(n)$$f(m)$$m=1,2,\dots$$n$$m=n$$g(n)$$\liminf g(n)/f(n)=0$$g(n)$$n$$n^{f(n)}$$n$.

Ich finde es auch interessant, einen Beweis durch Lücken in SAT zu sehen, wie in http://blog.computationalcomplexity.org/media/ladner.pdf . Ohne die NP-Anforderung ist dies ziemlich einfach: Es gibt eine Folge so dass keine Schaltkreisgröße SAT-Ketten der Länge erkennt ; Beschränken Sie SAT für einige auf Zeichenfolgen der Länge .$n_1<n_2<\dots$$(n_k)^k$$n$$n_{2^{2^i}}$$i$

(NPI P / poly) (P NP)$\nsubseteq$$\implies$$\neq$