¿LOGLOG = NLOGLOG?

Defina LOGLOG como la clase de lenguajes que se pueden calcular en el espacio O (loglog n) mediante una máquina de Turing determinista (con acceso bidireccional a la entrada). De manera similar, defina NLOGLOG como la clase de lenguajes que se pueden calcular en el espacio O (log log n) mediante una máquina de Turing no determinista (con acceso bidireccional a la entrada). ¿Realmente no se sabe que estas clases difieren?

Solo pude encontrar algunas encuestas anteriores y un teorema de que si son iguales, entonces L = NL (¡lo cual no es solo un argumento de relleno trivial!), Pero de alguna manera siento que separar estas clases no puede ser tan difícil. Por supuesto, podría estar completamente equivocado, pero si cada segundo bit de la entrada son los números del 1 al n en orden creciente en binario, separados por algunos símbolos, entonces las máquinas ya pueden aprender loglog n y con cada segundo segundo bit podemos ingrese un problema que puede engañar a una máquina determinista pero no a una no determinista. Todavía no veo exactamente cómo se podría hacer esto, pero parece un posible enfoque, ya que con este truco básicamente podemos ingresar un árbol binario de registro de profundidad junto con su estructura en lugar de la cinta lineal habitual.

La entrada en el complejo zoológico es sorprendentemente detallada; afirma que NLOGLOG = co-NLOGLOG en el documento

Cálculos no deterministas en espacio sublogarítmico y constructibilidad espacial , Viliam Geffert, SIAM Journal on Computing, 1991.

Pero después de una breve lectura, no veo ningún reclamo sobre el hecho de que NLOGLOG está cerrado bajo el complemento; tal vez se necesita una mirada más profunda. Y el resultado principal que tienen es que no hay funciones monótonas ilimitadas no deterministas completamente construibles en el espacio que aumenten funciones para . Se sabe que si tales funciones existen, entoncess ( n ) = o ( log n $s(n)$$s(n) = o(\log n)$

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

Y en la conclusión, el autor afirmó que "... este problema principal de separación sigue abierto ".

Como dijo @chazisop, las relaciones de estas clases de complejidad de bajo nivel dependen de los modelos, y en la entrada del zoológico se afirma que

"Hay varias definiciones posibles de esta clase; la más común es la clase de lenguajes que se pueden calcular en el espacio O (log log n) mediante una máquina de Turing determinista con acceso bidireccional a la entrada".

Lo cual coincide con su definición y también con la del artículo.