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)$

— 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