Schaltkreise mit Orakeln gegen Turingmaschinen mit Orakeln

13

Einfach ausgedrückt: Was ist die Entsprechung zwischen Turingmaschinen mit Orakeln und einheitlichen Stromkreisfamilien mit Orakeln? Wie werden letztere definiert, um dasselbe Rechenmodell für eine bestimmte Oracle Turing-Maschine zu erhalten?

Dies mag eine elementare Frage sein, aber es ist nicht klar, wo man hinschaut, und ich bin der Typ, der gerne sicherstellt, dass meine Fundamente hochwertigen Mörtel verwenden. Wenn es eine Standardreferenz gibt, weisen Sie mich bitte darauf hin. (Papadimitrious Buch zum Beispiel scheint überhaupt keine Schaltkreise mit Orakeln zu beschreiben.)

Meine Arbeitshypothese lautet: Eine einheitliche Schaltkreisfamilie mit Zugang zu einem Orakel (z. B. zur Lösung eines NP-vollständigen Problems) ist wie folgt definiert:

  • Man definiert eine unendliche Familie von "Orakelgattern" O n  , eines für jede Schaltungsgröße n, von denen jedes eine Funktion f n berechnet  : {0,1} cn  → {0,1} für eine Konstante c.

  • Die Funktionen f n durch die Oracle - Gatter O berechnet n soll im folgenden Sinne "gleichförmig" sein: für jeden n <N und x  ∈ {0,1} n , benötigen wir f n ( x ) = f N (0 C ( N - n)  x  ) --- das heißt, die Orakeltore müssen eine konsistente und erweiterbare "Codierung" ihrer Eingaben verwenden.

  • Man definiert dann eine einheitliche Schaltkreisfamilie, in der die Orakel-Gatter zu den zulässigen Operationen für den Schaltkreis gehören, wodurch die Schaltung auf die Eingangsgröße n beschränkt wird, um das Gatter On zu verwenden .

Ich stelle mir vor, dass einige der oben genannten Optionen willkürlich festgelegt werden können, ohne die Allgemeinheit zu verlieren. Was mich interessiert, ist eine Referenz für die Korrespondenz oder zumindest eine Beschreibung, wie die obige Beschreibung geändert werden kann, um die Standardbeschreibung zu erhalten.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
quelle
Da ich weiß, dass Sie mit Quanteninformation arbeiten, würde ich John Watrous Umfrage zur Komplexität von Quantenrechnungen empfehlen, in der er auch über Orakel in Quantenschaltungen spricht und das Orakel in Überlagerung abfragt.
Robin Kothari
Der Artikel von Watrous ist auch eine gute Referenz. Es stellte sich jedoch heraus, dass ich in diesem Fall der Vorstellung, dass jemand eine relativierte Schaltkreisfamilie auf eine Weise definieren möchte, die nicht dem bloßen Testen des gleichen Prädikats für verschiedene endliche Stringlängen durch Sein entsprach, irgendwie nicht zustimmen musste daran erinnert, dass die Semantik eines Orakels klassisch die Zugehörigkeit zu einer Gruppe anzeigt. Es stellte sich heraus, dass Zeichnungen von Schaltungstoren mit den Symbolen "∈A?" auf ihnen war alles was ich brauchte.
Niel de Beaudrap

Antworten:

19

Die beste Referenz für relativierte Schaltungen ist Chris Wilsons Artikel "Relativized NC" http://www.springerlink.com/content/u727654246wu8662/

Die zweite Bedingung, die Sie haben (abwärtsgerichtete Schließung von O_n), ist nicht erforderlich, um die Äquivalenz zwischen P ^ O und Schaltkreisen mit einheitlicher Polygröße mit Orakel O zu erhalten bis O_m für m größer als die Schaltkreisgröße.

Lance Fortnow
quelle
In Wilsons Aufsatz gibt es keinen expliziten Kommentar zu den Orakeltoren selbst; Aber im Nachhinein ist meine zweite Bedingung, wenn Sie das Orakel als Repräsentation der Zugehörigkeit zu einer Reihe von Booleschen Zeichenfolgen wie bei TMs ernst nehmen, nur eine Nicht-Frage (dh es versteht sich von selbst). Nach Ihrer Beobachtung der Überflüssigkeit meiner dritten Bedingung genügt es dann, eine unendliche Familie von Toren zu haben, die über die Zugehörigkeit zu A für eine bestimmte endliche Saitengröße entscheiden. Das ist für mich in Ordnung; Ich wünschte, ich hätte daran gedacht, Earler.
Niel de Beaudrap
3
Anmerkungen für zufällige Zuschauer --- Wilsons Artikel definiert den Tiefenbeitrag eines Orakeltors auf k Bits als ceil (log k) in offensichtlicher Analogie zu früheren Arbeiten von Cook ("Eine Taxonomie von Problemen mit schnellen parallelen Algorithmen"). , Inform. And Control, 64). Es gibt eine technische Frage, ob beim Aufbau der Schaltkreise selbst Orakelabfragen zugelassen werden sollen (von denen jeder auch Orakel verwenden kann): Er merkt an, dass dies keine Rolle zu spielen scheint. Am Ende ist er jedoch unzufrieden mit der Existenz von A, für das NC_1 ^ A nicht in NSPACE ^ A (O (n ^ k)) enthalten ist, für jede k-Konstante.
Niel de Beaudrap