Hierarchia naprzemienna

Dzięki Immerman i Szelepcsényi wiadomo, że jeśli (nawet w przypadku funkcji niemożliwych do zbudowania w przestrzeni). ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ $f=\Omega(\log)$

W tym samym artykule Immerman stwierdza, że naprzemienna hierarchia przestrzeni logicznej się zawala, co oznacza, że (definicja ograniczonej naprzemiennej maszyny Turinga i tego, co jest hierarchię można znaleźć na wikipedii ). $\Sigma_j{\rm SPACE}(\log)={\rm NSPACE}(\log)$

Czy jest jakaś praca na temat naprzemiennej hierarchii przestrzeni dla ? W zeszłym tygodniu poprosiłem Immermana, który nie pamiętał, żeby coś takiego czytać. W języku angielskim chciałbym wiedzieć, czy istnieje jakiś pisemny dowód na to, że użycie dowolnego języka, który może być decydowany przez maszynę Turinga z alternatywnymi może być również zadecydowane przez niedeterministyczną maszynę Turinga z tym samym ograniczonym miejscem. $f=\Omega(\log)$ $j$

Moje pytanie naprawdę dotyczy znalezienia referencji, ponieważ myślę, że wymyśliłem dowód; ale myślę, że może to już być znane.

Może powinienem powiedzieć, co uważam za dwa główne problemy. Po pierwsze, jeśli , powiedzmy , wówczas niemożliwe jest skomponowanie do TM w celu uzyskania TM, co moglibyśmy zrobić z TM. Po drugie, istnieje jeden argument dla przypadku $f=O(n)$ $f=\log^2$ $SPACE(f)$ $SPACE(f)$ $\rm{LOGSPACE}$ $f=O(n)$ i jeden dla ale nadal istnieje pewien problem z fonction, który nie jest ani ani . $f=\Omega(n)$ $O(n)$ $\Omega(n)$

cc.complexity-theory reference-request space-bounded alternating-hierarchy Arthur MILCHIOR
źródło

Przydałoby się krótka definicja dwóch wspomnianych hierarchii.

Robin Kothari,

brakuje „s” w hierarchii

Suresh Venkat

Dodałem link do naprzemiennej przestrzeni i hierarchii oraz szybką definicję tego, co chciałbym w języku angielskim. W przypadku hierarchii wyroczni obawiam się, że poprawna definicja może być zbyt długa, a poza tym bezużyteczna, ponieważ ta klasa jest równa niedeterministycznemu obszarowi logowemu.

Arthur MILCHIOR

osobliwością hierarchii jest hierarchia, przy okazji. czy możesz to edytować?

Suresh Venkat

Edytowane. Obawiam się, że nigdy nie zwracałem na to uwagi.

Arthur MILCHIOR

Odpowiedzi:

$ALTS$ $SPACE(a(n),s(n))$ $a(n)$ $s(n)$

$AC^1$ $ALT$ $SPACE(\log n, \log n)$

$ALTS$ $SPACE(a(n),\log n) \subseteq NSPACE(a(n) \log n)$

Ryan Williams
źródło

Dziękuję Ci; wydaje się to naprawdę obiecujące. Nie mam pojęcia, gdzie zacząć szukać takiego artykułu. Dowód nie wydaje mi się trywialnym następstwem, ponieważ, niech M będzie TM w ASPACE (f, 2), niech M1 będzie częścią egzystencjalną, a M2 częścią uniwersalną. Nie możemy już uważać M2 za coSPACE (f) = SPACVE (f) TM, ponieważ powinniśmy wziąć wejście M1 na taśmę wejściową. Ale tak, z pewnością jest coś do zrobienia, używając bezpośrednio ich dowodu. Nawet jeśli nie pomyślałem o użyciu liczby „a (n)” na przemian.

Jeszcze

$ALTSPACE(a(n),s(n))$ $NSPACE(a(n)s(n))$ $a(n)$ $s(n)$

Połączenie tego z twierdzeniem Savitcha daje następujące wyniki:

$ALTSPACE(\log n, \log n)$ $SPACE((\log n)^4)$

Następstwo: Podobnie język obliczalny w przestrzeni wielomianowej z wielomianowo wieloma alternatywami występuje w deterministycznej przestrzeni wielomianowej.

$ALTSPACE$ $STA$

[B] L. Berman, „Złożoność teorii logicznych”, Theoretical Computer Science 11 (1980) 71-77.

Sam Buss
źródło