Ist

Im "letzten Absatz" der "ersten Seite" des folgenden Papiers:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , "Wenn NP polynomgroße Schaltkreise hat, dann ist MA = AM", Theoretical Computer Science, 1995.

Ich bin auf eine etwas kontraintuitive Behauptung gestoßen:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

Ich denke, die obige Identität leitet sich aus Folgendem ab:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

und

$(\Pi^P_2)^{NP} = \Pi^P_3$

Ersteres ist einfacher als geschrieben , was ziemlich seltsam ist!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Bearbeiten: In Anbetracht des Kommentars von Kristoffer unten möchte ich die folgende anregende Bemerkung aus Goldreichs Komplexitätsbuch (S. 118-119) hinzufügen :

Es sollte klar sein, dass die Klasse für zwei Komplexitätsklassen C 1 und C 2 definiert werden kann , vorausgesetzt, dass C 1 einer Klasse von Standardmaschinen zugeordnet ist, die auf natürliche Weise auf eine Klasse von Orakelmaschinen verallgemeinert wird. Tatsächlich wird die Klasse C C 2 1 nicht auf der Basis der Klasse C 1 definiert , sondern in Analogie dazu. Nehmen wir insbesondere an, dass C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$ist die Klasse von Mengen, die von Maschinen eines bestimmten Typs (z. B. deterministisch oder nicht deterministisch) mit bestimmten Ressourcengrenzen (z. B. Zeit- und / oder Raumgrenzen) erkannt (oder vielmehr akzeptiert) werden. Danach betrachten wir analog Oracle - Maschinen (dh desselben Typs und mit denselben Ressourcen Grenzen), und sagen , daß , wenn es einen ausreichenden Oracle Maschine existiert M 1 (dh dieser Art und Ressourcengrenzen) und eine Menge S 2 ≤ C 2, so dass M S 2 1 die Menge S akzeptiert .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

ist die Menge der Sprache, die von einer alternierenden Turing-Maschine im existenziellen und dann im universellen Zustand mit einem Orakel im NP bestimmt wird. Sowohl der universelle als auch der existentielle Teil können NP abfragen.${\Sigma_2^P}^{NP}$

In diesem Fall haben Sie sich also entschieden, dies als zu schreiben, und dann ist die Art und Weise, wie Sie es sich vorstellen sollten, ( N P N P A ∪ A ) (mit ∪ meine ich ein Orakel entweder für A oder für eine N P A Sprache).$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

Daher ist gleich ( N P ( N P N P ) ) N P, was sicherlich gleich ( N P N P N P ) ist, da jede Abfrage, die Sie an das N P- Orakel stellen könnten, Sie auch machen könnten zum N P N P Orakel.${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$

Von Arora und Barak (S. 102) . Theorem 5.12: "Für jedes , Σ p i = N P Σ i - 1 S A T ". Denken Sie daran, dass ∑ i S A T die QBF-Formel mit i Alternationen ist, die für ∑ p i vollständig ist . Dann ist ∑ p 2 = N P S A T und wenn SAT NP-vollständig ist, schreiben Sie einfach ∑ p 2 = N P $i\geq 2$$\sum_i^p=NP^{\sum_{i-1}SAT}$$\sum_{i}SAT$$i$$\sum_i^p$$\sum_2^p=NP^{SAT}$ , soweit so gut. Wenn Sie diese Notation aufi=3 erweitern, erhaltenSieN P N P N P , aber die letzten beiden "NPs" sind nur ein Orakel für die Sprache ∑ 2 SATmit höchstens 2 Abwechslungen. Es scheint mir, dass es nur eine Kurzschreibweise für Orakelzugriff ist.$\sum_2^p=NP^{NP}$$i=3$$NP^{NP^{NP}}$$\sum_{2}SAT$