Ist LOGLOG = NLOGLOG?

Definieren Sie LOGLOG als die Klasse von Sprachen, die von einer deterministischen Turing-Maschine (mit bidirektionalem Zugriff auf die Eingabe) in Raum O (loglog n) berechnet werden können. Definieren Sie NLOGLOG auf ähnliche Weise als die Klasse von Sprachen, die von einer nicht deterministischen Turing-Maschine (mit bidirektionalem Zugriff auf die Eingabe) in Raum O (log log n) berechnet werden kann. Ist nicht wirklich bekannt, dass sich diese Klassen unterscheiden?

Ich konnte nur einige ältere Umfragen und einen Satz finden, der besagt, dass es nicht so schwer sein kann, diese Klassen zu trennen, wenn sie gleich L = NL sind (was nicht nur ein triviales Auffüllargument ist!). Natürlich könnte ich mich völlig irren, aber wenn jedes zweite Bit der Eingabe die Zahlen von 1 bis n in aufsteigender Reihenfolge in binärer Reihenfolge sind, getrennt durch einige Symbole, dann können die Maschinen bereits loglog n lernen und mit jedem zweiten Bit können wir Geben Sie ein Problem ein, das eine deterministische Maschine täuschen kann, aber keine nicht deterministische. Ich verstehe noch nicht genau, wie das gemacht werden könnte, aber es fühlt sich wie ein möglicher Ansatz an, da wir mit diesem Trick im Grunde genommen anstelle des üblichen linearen Bandes einen binären Baum mit Tiefenprotokoll und seiner Struktur eingeben können.

Der Eintrag im Komplexitätszoo ist überraschend detailliert; es behauptet, dass NLOGLOG = Co-NLOGLOG in der Zeitung

Nichtdeterministische Rechnungen im sublogarithmischen Raum und Raumkonstruierbarkeit , Viliam Geffert, SIAM Journal on Computing, 1991.

$s(n)$$s(n) = o(\log n)$

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

Und in der Schlussfolgerung behauptete der Autor, dass "... dieses Hauptproblem der Trennung offen bleibt ."

Wie @chazisop sagte, hängen die Beziehungen dieser niederen Komplexitätsklassen von den Modellen ab, und es wird im Eintrag des Zoos angegeben, dass

"Es gibt mehrere mögliche Definitionen dieser Klasse; die gebräuchlichste ist die Klasse von Sprachen, die von einer deterministischen Turing-Maschine mit bidirektionalem Zugriff auf die Eingabe in Raum O (log log n) berechnet werden kann."

Was Ihrer Definition und auch der des Papiers entspricht.