Czy LOGLOG = NLOGLOG?

Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez niedeterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Czy naprawdę nie wiadomo, że te klasy się różnią?

Mogłem znaleźć tylko niektóre starsze ankiety i twierdzenie, że jeśli są równe, to L = NL (co nie jest tylko trywialnym argumentem wypełniającym!), Ale jakoś czuję, że oddzielenie tych klas nie może być takie trudne. Oczywiście mogę się całkowicie mylić, ale jeśli co drugi bit danych wejściowych to liczby od 1 do n w porządku rosnącym w systemie binarnym, oddzielone niektórymi symbolami, to maszyny mogą już nauczyć się logarytmu n, a co drugi bit możemy wprowadź problem, który może oszukać maszynę deterministyczną, ale nie niedeterministyczną. Nie wiem jeszcze dokładnie, jak można to zrobić, ale wydaje mi się to możliwym podejściem, ponieważ dzięki tej sztuczce możemy w zasadzie wprowadzić logarytmiczne drzewo głębokości i drzewo binarne wraz z jego strukturą zamiast zwykłej taśmy liniowej.

cc.complexity-theory reference-request space-bounded

— domotorp
źródło

Z szybkiego wyszukiwania znalazłem artykuł „Computing with Sublogarithmic Space” autorstwa Macieja Liskiewicza i Rudigera Reischuka. Wydaje się również, że w przestrzeni sublogarytmicznej relacje klas zależą w dużej mierze od zastosowanego modelu.

— chazisop

@chazisop: jest to jedna z ankiet, które również znalazłem, wszystko wydaje się mieć co najmniej dziesięć lat na ten temat.

— domotorp

Myślę, że @Kaveh jest odsyłany do tego postu .

— Hsien-Chih Chang 24 之

Twoja pamięć jest rzeczywiście niejasna, twierdzenie jest takie, że każda TM używająca spacji o (log log n) musi być regularna.

— domotorp

@domotorp: obie instrukcje są twierdzeniami, ale dla

potrzebujesz pojedynczej taśmy. (Oczywiście dla

możesz również założyć jedną taśmę, ponieważ tłumaczenie wielu taśm na jedną taśmę nie zwiększa przestrzeni.) Odniesienie, którego szukała Neal Young to: Kobayashi (1985) ( dx.doi.org/10.1016/0304-3975(85)90165-3 ) budowanie z Hennie (1965) ( dx.doi.org/10.1016/S0019-9958(65)90399-2 ), który wykazał, że TM z liniami w jednym czasie decydują tylko o zwykłych językach i wprowadziły sekwencje krzyżowania.o(nlogn) $o(n \log n)$

SPACE(o(loglogn)) $SPACE(o(\log \log n))$

— Joshua Grochow

Wpis w złożoności zoo jest zaskakująco szczegółowe; twierdzi, że NLOGLOG = co-NLOGLOG w gazecie

Niedeterministyczne obliczenia w przestrzeni sublogarytmicznej i konstruowaniu przestrzeni , Viliam Geffert, SIAM Journal on Computing, 1991.

Ale po krótkim czytaniu nie widzę żadnych roszczeń dotyczących faktu, że NLOGLOG jest zamknięty pod uzupełnieniem; może potrzebne jest głębsze spojrzenie. Ich głównym skutkiem jest to, że nie ma niedeterministycznych, nieograniczonych, nieograniczonych, monotonicznych funkcji zwiększających dla . Wiadomo, że jeśli takie funkcje istnieją, to $s(n)$ $s(n) = o(\log n)$

. $\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$

Na zakończenie autor stwierdził, że „ten główny problem separacji pozostaje otwarty ”.

Jak powiedział @chazisop, relacje tych klas złożoności niskiego poziomu zależą od modeli i we wpisie do zoo stwierdzono, że

„Istnieje kilka możliwych definicji tej klasy; najczęstszą jest klasa języków, którą można obliczyć w przestrzeni O (log log n) przez deterministyczną maszynę Turinga z dwukierunkowym dostępem do danych wejściowych.”

Co jest zgodne z twoją definicją, a także z definicją papieru.

— Hsien-Chih Chang 張顯之
źródło

Myślę, że twierdzi tylko, że NLOGLOG = co-NLOGLOG. Nie mogłem też znaleźć tego stwierdzenia w streszczeniu artykułu, chociaż nie mogłem otworzyć całego artykułu.

— domotorp

@domotorp: Masz rację. Czuję się naprawdę zawstydzona moją błędną odpowiedzią ... Jestem zbyt zmęczony, nawet źle odczytałem zdania, Może powinienem zrobić sobie przerwę na Święta.

— Hsien-Chih Chang 之之