Raum wechselnde Hierarchie

Dank Immerman und Szelepcsényi ist bekannt, dass wenn (auch für nicht raumkonstruierbare Funktionen). ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ $f=\Omega(\log)$

In der gleichen Arbeit, Immerman Zustand , dass die logspace Wechselhierarchie kollabiert, bedeutet dies , dass (die Definition des begrenzten alternierenden Turingmaschine und von dem, was Eine Hierarchie finden Sie auf Wikipedia ). $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Gibt es ein Papier über die alternierende Raumhierarchie für ? Ich fragte letzte Woche Immerman, der sich nicht erinnern konnte, so etwas gelesen zu haben. In Englisch würde ich gerne wissen, ob es einen schriftlichen Beweis dafür gibt, dass die Verwendung einer Sprache, die von einer Turing-Maschine mit Wechseln entschieden werden kann, auch von einer nicht deterministischen Turing-Maschine mit dem gleichen begrenzten Raum entschieden werden kann. $f=\Omega(\log)$ $j$

Bei meiner Frage geht es wirklich darum, eine Referenz zu finden, denn ich glaube, ich habe den Beweis gefunden. aber ich vermute, dass es vielleicht schon bekannt ist.

Vielleicht sollte ich sagen, was meiner Meinung nach die beiden Hauptprobleme sind. Wenn , lassen Sie uns sagen , dann ist es unmöglich, zu TM zu komponieren, um ein TM zu erhalten, was wir tun könnten TM. Zweitens gibt es ein Argument für den Fall $f=O(n)$ $f=\log^2$ $SPACE(f)$ $SPACE(f)$ $\rm{LOGSPACE}$ $f=O(n)$ und eins für aber es gibt immer noch ein Problem für die Funktion, die weder noch . $f=\Omega(n)$ $O(n)$ $\Omega(n)$

cc.complexity-theory reference-request space-bounded alternating-hierarchy Arthur MILCHIOR
quelle

Es wäre hilfreich, wenn Sie eine kurze Definition der beiden von Ihnen genannten Hierarchien einfügen könnten.

Robin Kothari

Fehlen eines 's' in Hierarchien

Suresh Venkat

Ich habe einen Link für raumbegrenzte Abwechslung und Hierarchien hinzugefügt und eine kurze Definition auf Englisch von dem, was ich möchte. Ich fürchte, eine korrekte Definition ist zu lang und trotzdem nutzlos, da diese Klasse nicht deterministischem Logspace entspricht.

Arthur MILCHIOR

Der Singular der Hierarchien ist übrigens Hierarchie. kannst du das bearbeiten

Suresh Venkat

Bearbeitet Ich fürchte, ich habe das nie beachtet.

Arthur MILCHIOR

Antworten:

Sei - die Klasse von Problemen, die mit Wechsel im -Raum lösbar sind . In der Blütezeit der Parallelkomplexitätstheorie tauchte diese Klasse ziemlich oft auf. $ALTS$ $SPACE(a(n),s(n))$ $a(n)$ $s(n)$

Zum Beispiel ist die Klasse nur - . Daher stelle ich mir vor, dass es viele Artikel zu Ihrem Thema gibt, obwohl sie möglicherweise nicht in der von Ihnen verwendeten Notation geschrieben sind. $AC^1$ $ALT$ $SPACE(\log n, \log n)$

Für den Rest Ihrer Frage denke ich, dass man in der Lage sein sollte, - direkt zu beweisen von Immerman-Szelepcsényi. $ALTS$ $SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$

Ryan Williams
quelle

Vielen Dank; Das scheint wirklich vielversprechend. Ich habe nur keine Ahnung, wo ich anfangen soll, nach einem solchen Artikel zu suchen. Der Beweis scheint mir keine triviale Konsequenz zu sein, denn sei M ein TM in ASPACE (f, 2), sei M1 der existentielle Teil und M2 der universelle Teil. Wir können M2 nicht mehr als coSPACE (f) = SPACVE (f) TM betrachten, da wir die Eingabe von M1 in das Eingabeband übernehmen sollten. Aber ja, es gibt sicherlich etwas zu tun, wenn man ihren Beweis direkt verwendet. Auch wenn ich nicht eine Zahl "a (n)" als Alternative verwendet habe.

Nochmals vielen

$ALTSPACE(a(n),s(n))$ $NSPACE(a(n)s(n))$ $a(n)$ times backtracking in the "obvious" fashion. Each iteration uses only $s(n)$ space to store the counts of reachable configurations.

Combining this with Savitch's theorem gives the following results:

Corollary: $ALTSPACE(\log n, \log n)$ is in $SPACE((\log n)^4)$ . More generally, a language computable in polylogarithmic space with polylogarithmically many alternations is computable in deterministic polylogarithmic time.

Folgerung: Ähnlich ist eine Sprache, die im Polynomraum mit polynomiell vielen Abwechslungen berechenbar ist, im deterministischen Polynomraum.

Ich kenne keine Referenzen für diese $ALTSPACE$ Ergebnisse oder ob sie schon einmal bemerkt wurden, oder sogar für die Notation. Leonard Berman [B] verwendete die Notation " $STA$ "für" Raum / Zeit / Wechsel "Klassen.

[B] L. Berman, "Die Komplexität logischer Theorien", Theoretical Computer Science 11 (1980) 71-77.

Sam Buss
quelle