Weltraumgebundene TMs und Orakel

20

Im Allgemeinen zählt das Abfrageband für ein Orakel für die räumliche Komplexität eines TM. Es erscheint jedoch plausibel, nur ein beschreibbares Orakelband zuzulassen (wie es bei L-Platz-Verkleinerungen verwendet wird).

Ist eine solche Konstruktion sinnvoll? Ergibt es irgendwelche besonders absurden Ergebnisse?

cc.complexity-theory space-bounded oracles Jeremy Hurwitz
quelle

Wie lesen Sie die Antwort, wenn Sie ein TM mit einem Oracle-Band haben, das nur zum Schreiben bestimmt ist? Dann kannst du das Orakel einfach vergessen.

Marcos Villagra

1

Es gibt heikle Fragen bei der Entscheidung, was die richtige Definition des Oracle-Zugriffs für weltraumgebundene Maschinen ist. Siehe "Relativierung kleiner Komplexitätsklassen und ihre Theorien" von Klaus Aehlig, Stephen Cook und Phuong Nguyen, CSL 2007.

Kaveh

@Marcos: Ich glaube, die Antwort ist einfach der resultierende interne Zustand der Maschine und wird nicht auf das Orakelband geschrieben.

Joe Fitzsimons

Was ist die Referenz für diese Definition von weltraumgebundenen Orakelmaschinen?

Miforbes

10

Ich denke, eine überraschende Tatsache ist, dass der Satz von Savitch in diesem Modell nicht "offensichtlich" relativiert wird. Das heißt, kann man sehen , dass und in diesem Modell, und wir derzeit nicht wissen, dass $PSPACE^P=EXPTIME$ $NPSPACE^P=NEXPTIME$ (und Savitch Theorem in diesem Zusammenhang scheint es nicht zu geben). Mich würde interessieren, ob dies auf "nachweislich" nicht-relativierend gedrückt werden kann. $EXPTIME=NEXPTIME$

Man kann auch beobachten, dass in diesem Modell ist. $NL^{NL}=NL^L=NP$

Ich denke jedoch, dass dieses Modell in Bezug auf Fragen der Relativierung im Satz der Raumhierarchie zumindest eine Überlegung wert ist. Auch in gewissem Sinne möchte ich Poly-Größe Abfragen machen . $L^A$ $A$

miforbes
quelle

1

Eines habe ich vergessen: Als NL = coNL sollten wir NL ^ NL = NL wollen, aber wenn NL ^ NL = NP in diesem Modell ist, können wir NL = coNL nicht verwenden, um die "NL-Hierarchie" zu kollabieren. In einer anderen Vorstellung von raumgebundenen Orakeln kollabiert die Hierarchie tatsächlich (siehe Immermans NL = coNL-Artikel für Referenzen).

Miforbes

Haben Sie eine Referenz? Ich hätte

erwartet . In der Tat sei

eine rekursiv aufzählbare Sprache,

ein TM, der

und

ein TM erkennt , die eine Eingabe und eine Zahl

von "1" lesen, und dann

für diese Eingabe in

Schritten simuliert . Dann könnte ich ohne Leerzeichen die Eingabe auf das Orakelband kopieren, die Nummer 1 erraten und

abfragen .

N S P A C E (0)^{P} = R E

$\rm{NSPACE(0)^P=RE}$

L

$L$

M

$M$

L

$L$

M^{'}

$M'$

n

$n$

M

$M$

n

$n$

M^{'}

$M'$

Arthur MILCHIOR

9

Dies könnte Ihre Frage nicht beantworten (was ich ehrlich gesagt nicht ganz verstehe), aber ich denke, es ist im gleichen Sinne. Es ist bekannt, dass es einen Unterschied in der Reduzierbarkeit zwischen einem Logspace TM mit einem Orakelband und einem mit Zugriff auf mehrere Orakelbänder gibt. Außerdem hat der folgende Begriff der Logspaceness nette Eigenschaften: Der TM kann nur eine logarithmische Menge an Speicherplatz auf seinem Arbeitsband verwenden, aber er kann eine polynomische Menge an Speicherplatz auf seinen Orakelbändern verwenden.

Referenz: http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf

Aaron Sterling
quelle

3

NSPACE (0) P = RE, was meiner Meinung nach ein bisschen absurd ist.

In der Tat sei L eine rekursiv aufzählbare Sprache, M ein TM, der L und M 'ein TM erkennt, die eine Eingabe und eine Zahl n von "1" lesen, und dann M für diese Eingabe in n Schritten simuliert. Dann könnte ich ohne Leerzeichen die Eingabe auf das Orakelband kopieren, die Nummer 1 erraten und M 'abfragen.

Dann wird M 'annehmen, wenn M annehmen und eine Eingabe haben, die groß genug ist, um polynomiell zu sein.

Arthur MILCHIOR
quelle

Weltraumgebundene TMs und Orakel

Antworten: