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.

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 s ( n ) dla s ( n ) = o ( log n ) . Wiadomo, że jeśli takie funkcje istnieją, to$s(n)$$s(n) = o(\log n)$

S P A C E [ s ( n ) ] ≠ N S P A C E [ s ( 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.