Gibt es eine endgültige Referenz für Turingmaschinen mit mehreren Orakelbändern?

Der größte Teil der Literatur scheint sich mit Maschinen mit einzelnen Orakeln für bestimmte Probleme zu befassen, es scheint jedoch einige Veröffentlichungen zu geben, die Maschinen mit mehreren Orakeln betrachten. Gibt es eine gute Arbeit oder These, die einen Überblick darüber gibt, was über solche Maschinen bekannt ist? Insbesondere interessiere ich mich für P mit mehreren Orakeln.

oracles turing-machines Joe Fitzsimons
quelle

Wenn Sie nur eine endliche Anzahl N von Orakeln möchten, können Sie ein N-in-1-Verbundorakel definieren, indem Sie die ersten Protokollbits (N) des zusammengesetzten Orakels verwenden, um anzugeben, welches Unterorakel Sie abfragen möchten. Vermisse ich etwas

Niel de Beaudrap

Ja, daran hatte ich gedacht. Ich interessiere mich jedoch für bestimmte Orakelsätze, und daher erscheint es natürlicher, sie separat zu betrachten als als zusammengesetztes Objekt. Ich dachte, vielleicht gibt es einige schöne Ergebnisse in dieser Richtung.

Joe Fitzsimons

Fügt aus Neugier mehr mehrere Orakel mehr Rechenleistung in Bezug auf eine einzelne Orakelmaschine hinzu? Es scheint mir, dass nein, weil Sie nur das Orakel nehmen, das der Sprache in der höchsten Komplexitätsklasse entspricht. Eine feste Anzahl von Orakeln verlangsamt die Maschine um eine Konstante.

Marcos Villagra

Ich bin mit Marcos 'Kommentar über das stärkste Orakel, das die anderen subsumiert, aber ich bin interessiert, was Sie jetzt im Sinn hatten!

Daniel Apon

Denken Sie darüber nach, unendlich viele Orakel zuzulassen, wobei das TM auswählen darf, welches Orakel abgefragt werden soll? Bei einem solchen Aufbau kann es einen interessanten Unterschied zwischen einem Satz von Orakeln geben, bei denen jedes streng schwächer war als irgendein anderes Orakel Q, und Q selbst.

András Salamon

Antworten:

Hier ist ein neueres Papier, das einen Unterschied zwischen einzelnen und mehreren durch Kryptographie motivierten Orakeln gibt:

Donald Beaver und Joan Feigenbaum. Ausblenden von Instanzen in Multioracle-Abfragen . STACS 1990. Springer Lecture Notes in Computer Science, 1990, Band 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
quelle

Nur eine Frage, ich nehme an, dass das Konzept des Multi-Orakels nur dann Sinn macht, wenn die Orakel aus bestimmten (wahrgenommenen?) Sicherheitsgründen nicht ineinander kollabiert werden können.

Ahmed Masud

Hier ist ein älteres Dokument, das Sie möglicherweise hilfreich finden: Logspace-Maschinen mit mehreren Oracle-Bändern von Nancy Lynch am MIT ( PDF ). Insbesondere Satz 2.2 auf PDF-Seite 5 könnte die Art von Dingen sein, nach denen Sie suchen. Es gibt auch einen Abschnitt über Hierarchien, die durch eine unterschiedliche Anzahl von Orakelbändern pro Maschine definiert sind.

Haftungsausschluss nachträglich: Es sieht so aus, als ob hier eine ähnliche Frage und (noch ähnlichere) Antwort gegeben wurden .

Daniel Apon
quelle