Ist

17

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:

(Σ2PΠ2P)NP=Σ3PΠ3P

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

(Σ2P)NP=Σ3P

und

(Π2P)NP=Π3P

Ersteres ist einfacher als geschrieben , was ziemlich seltsam ist!(NPNP)NP=NPNPNP

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 1C1C2C1C2C1C1C2C1C1ist 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 2C 2, so dass M S 2 1 die Menge S akzeptiert .SC1C2M1S2C2M1S2S

MS Dousti
quelle
4
Aber ... ist dasselbe wie N P N P ? Oder fehle ich hier etwas? (NPNP)NPNPNP
Antonio E. Porreca
5
Hüten Sie sich vor den Gefahren der Orakelnotation. Wir haben den Begriff des Anhängens von Orakeln an eine Klasse von Sprachen nicht definiert. Nur für Sprachklassen, die durch ein Rechenmodell definiert sind, an das Orakel angehängt werden können. Somit ist in gewissem Sinne nicht sofort gut definiert. (NPNP)NP
Kristoffer Arnsfelt Hansen
2
Nun, ich stimme zu, dass der übliche Begriff „ als Exponent einer Klasse setzen“ im Allgemeinen schlecht definiert ist. Das zugrunde liegende Rechenmodell von N P N P ist jedoch genau definiert (ein Polytime-NTM mit einem Orakel für ein N P -vollständiges Problem), und das Hinzufügen eines weiteren Orakels dazu, wie in ( N P N P ) N P , scheint unkompliziert zu sein mir. Ich ging davon aus, dass das zweite Orakel überflüssig ist. Es würde mich freuen zu wissen, ob das Symbol ( N P N P ) N P andere Interpretationen zulässt.NPNPNPNP(NPNP)NP(NPNP)NP
Antonio E. Porreca
1
Nach dieser Interpretation würde sich die Klasse nicht ändern. Dies ist jedoch nicht die richtige Interpretation für die Relativierung von Lautemans 'Beweis, wie in dem in der Frage erwähnten Aufsatz ausgeführt.
Kristoffer Arnsfelt Hansen
1
Sadeq: Niemand behauptet, die Aussage in der Zeitung sei falsch.
Kristoffer Arnsfelt Hansen

Antworten:

13

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.Σ2PNP

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 AA ) (mit meine ich ein Orakel entweder für A oder für eine N P A Sprache).(NPNP)A(NPNPAA)ANPA

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.Σ2PNP(NP(NPNP))NP(NPNPNP)NPNPNP

Arthur MILCHIOR
quelle
1
Entschuldigung, ich habe es nicht verstanden. Kannst du etwas mehr erklären?
MS Dousti
Ich hoffe, die Bearbeitung macht mehr
Sinn
Sehr gut danke. Das macht sehr viel Sinn.
MS Dousti
4

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 Ni2ip=NPi1SATiSATiip2p=NPSAT , 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 Sprache2 SATmit höchstens 2 Abwechslungen. Es scheint mir, dass es nur eine Kurzschreibweise für Orakelzugriff ist.2p=NPNPi=3NPNPNP2SAT

Marcos Villagra
quelle