Sind Orakel assoziativ?

11

Diese Frage mag eine offensichtliche Antwort haben ... aber hier ist die Frage trotzdem. Intuitiv ist es die folgende plausible Aussage: "Eine Maschine mit einer Subroutine A, die wiederum eine Subroutine B hat, ist dieselbe wie eine Maschine mit einer Subroutine A, die Zugriff auf Subroutine B hat".

Um dieses Problem formal zu definieren, verwende ich eine unkonventionelle Notation. Wenn ich sage , gebe ich A ein Orakel für ein B - C o m p l e t e Problem. zB N P N P = N P S A T = Σ 2 . Mit dieser „neuen“ Notation ist es möglich , zu definieren A B C , und so weiter. Meine Frage ist, istABABCompleteNPNP=NPSAT=Σ2ABC

  • Ist dies eine gültige Denkweise über Orakel?
  • ist (AB)C=A(BC)

Zum Beispiel ist (NPNP)NP=Σ2NP=NPΣ2=NP(NPNP)

Ich kann mir keine offensichtlichen Gegenbeispiele zu dieser Regel vorstellen. Jemand?

gabgoh
quelle
Haben Sie meine Frage gesehen: cstheory.stackexchange.com/q/972/873 ?
MS Dousti
1
Dies ist eine etwas allgemeinere Frage, aber Sadeqs Frage ist ziemlich relevant, und insbesondere die Kommentare über die Missbildung von A ^ B ^ C, wenn A ^ B kein Rechenmodell ist
Suresh Venkat
nein, aber genau das habe ich letzte Nacht mit dem Kopf gegen die Wand geschlagen, worüber diese Frage motiviert war!
Gabgoh
Siehe auch diese Frage .
Kaveh

Antworten:

5

Wie Venkat in Kommentaren sagte, scheint es schwierig zu sein, Ihre Definition für Orakel zu verstehen, die nicht als eine maschinelle Charakterisierung definiert ist.

Sei die Menge von TM in A mit einem Orakel, das eine Maschine in ist ( B mit einem Orakel in einer Maschine in C ). Es ist offensichtlich, dass eine Maschine in A C aufrufen kann : Sie ruft nur die Maschine in B auf und fordert sie auf, die Nachricht direkt an C weiterzuleiten .A(BC)ABCACBC

Ich denke, wäre eine Maschine in A , die ein Orakel in C oder ein Orakel nennen kann (eine Maschine in B , die eine Maschine in C nennen kann ), also ist es genau dieselbe Definition.(AB)CACBC

Schließlich möchten Sie vielleicht , das sich sicherlich von den beiden anderen unterscheidet (nehmen Sie einfach B = C = N P und A = P , dann A B , C = N P c o N P, während A ( B C. ) = Σ P 2Π p 2 .AB,CB=C=NPA=PAB,C=NPcoNPA(BC)=Σ2PΠ2p

Arthur MILCHIOR
quelle
4
Seien Sie vorsichtig: P ^ NP enthält NP∪coNP, aber es ist nicht bekannt oder es wird angenommen, dass es NP∪coNP entspricht. In ähnlicher Weise ist nicht bekannt, dass P ^ (NP ^ NP) gleich Σ2P∪Π2P ist.
Tsuyoshi Ito
1
@ Tsuyoshi, danke für die Bemerkung, ich weiß nicht, warum ich das gedacht habe. In der Tat ist es klar, dass P N P ist , wenn ist . Sei A und B NPcomplte und coNPcomplete Probleme, dann das Problem, das Eingabe ( x , y ) nimmt und wahr beantwortet, wenn x A und y B in P N P, aber nicht in N P c o N P ist . NPcoNPPNPAB(x,y)xAyBPNPNPcoNP
Arthur MILCHIOR
3

Ich würde Folgendes als Kommentar schreiben, aber es war zu lang, um hinein zu passen.

Beschreiben wir zunächst die Bedeutung von „Algorithmen in Klasse mit einem Orakel für eine Sprache A.“ (Die Notwendigkeit dafür wurde von Tsuyoshi Ito hervorgehoben). Wir werden die gleiche Konvention verwenden, die Ladner und Lynch verwendet haben . Die Konvention wird von Bennett & Gill gut beschrieben :C

kann auf verschiedene Arten definiert werden, je nachdem, wie das Abfrageband behandelt wird. Wir folgen den Konventionen von Ladner und Lynch [LL]: Das Abfrageband wird nicht gegen den gebundenen Speicherplatz berechnet, aber um zu verhindern, dass es als Arbeitsband verwendet wird, ist das Abfrageband einseitig und nur zum Schreiben bestimmt und wird gelöscht automatisch nach jeder Abfrage. (Simon [Si] behandelt das Abfrageband als eines der Arbeitsbänder, ein Zwei-Wege-Lese- / Schreibband, das gegen den gebundenen Raum berechnet wird. Die Ladner-Lynch-Definition ist weniger restriktiv und möglicherweise natürlicher, da es sich um ein zufälliges Orakel handeltA L O G S P A C E A.LOGSPACEAALOGSPACEA gilt mit Wahrscheinlichkeit 1 für [LL], aber nicht für [Si])

[LL] RE LADNER UND NA LYNCH, Relativierung von Fragen zur Berechenbarkeit des Protokollraums , Math. Systems Theory, 10 (1976), S. 19-32.

[Si] J. SIMON, Zu einigen zentralen Problemen der Computerkomplexität , Tech. Rep TR 75-224, Institut für Informatik, Cornell University, Ithaca, NY, 1975.

Die Standarddefinition von Komplexitätsklassen von Orakelmaschinen lautet wie folgt: B und C seien Komplexitätsklassen . Dann ist ein legitimes Komplexitätsklasse, definiert als X = L C B L . Hier repräsentiert B L die Komplexitätsklasse von Entscheidungsproblemen, die durch einen Algorithmus in Klasse B mit einem Orakel für eine Sprache L lösbar sind.X=BCX=LCBLBL

Da X eine legitime Komplexitätsklasse ist, können wir für jede Komplexitätsklasse A von Komplexitätsklassen und X A = ( B C ) A sprechen .AX=A(BC)XA=(BC)A

  • bezieht sich auf die Komplexitätsklasse von Entscheidungsproblemen, die durch einen Algorithmus in Klasse A mit einem Orakel für jede Sprache L 'X = L C B L lösbar sind . Mit anderen Worten, A X = L '{ L C B L } A L ' .AXLX=LCBLAX=L{LCBL}AL

  • bezieht sich auf die Komplexitätsklasse von Entscheidungsproblemen, die durch einen Algorithmus in der Klasse X = L C B L mit einem Orakel für jede Sprache L 'A lösbar sind. Mit anderen Worten, X A = L 'A X L ' = L 'A ( L C B L ) L ' .XAX=LCBLLAXA=LAXL=LA(LCBL)L

Anspruch: .(BL1)L(BL2)L=(BL)L1L2

Side Note: Since it's 3:00 AM now, I'm too sleepy to check the validity of the above claim! I think it's valid & elementary to prove, yet it's nice to see the actual proof.

Daher kann man schreiben .XA=LA(LCBL)L=LC,LA(BL)L

Beispiel

X=PNPcoNPXNPcoNPNPXNP=(PNP)NP

Epilog

Eine fruchtbare Diskussion mit Tsuyoshi Ito ergab (für mich), dass es nicht einfach ist, eine Komplexitätsklasse doppelt zu relativieren. Tatsächlich scheint es sogar problematisch zu sein, eine zu definieren. Ich sollte auf jeden Fall mehr studieren, um zu sehen, ob jemals eine zufriedenstellende Definition gegeben wird. In der Zwischenzeit freue ich mich über jeden Kommentar, der zur Lösung dieses Problems verwendet werden kann.

MS Dousti
quelle
4
Wie ich zu einer anderen Frage kommentiert habe , hat „Algorithmus in Klasse B mit einem Orakel für eine Sprache L“ im Allgemeinen keine allgemein akzeptierte Definition.
Tsuyoshi Ito
@ Tsuyoshi: Ich habe die Antwort bearbeitet, um darzustellen, welche Definition ich verwende. Entfernt es die Missbildung?
MS Dousti
Nein. Der hinzugefügte Teil definiert nur, was LOGSPACE ^ A bedeutet, nicht was B ^ A für so etwas wie B = NP ^ NP bedeutet.
Tsuyoshi Ito
AXACXC
4
Leider ist Ihre „natürliche Anforderung“ tatsächlich nicht so natürlich. Obwohl PSPACE⊆IP und es eine natürliche und allgemein akzeptierte Definition von IP ^ A für jede Sprache A gibt (der Prüfer erhält einen Orakelzugriff auf A), ist bekannt, dass PSPACE ^ A⊈IP ^ A mit der Wahrscheinlichkeit 1 für einen Zufall Orakel A; siehe Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan und Rohatgi 1994 . Wie gesagt, es gibt meines Wissens keine allgemein akzeptierte Definition von C ^ A für eine beliebige Komplexitätsklasse C. (mehr)
Tsuyoshi Ito