LOGLOG = NLOGLOG?

Définissez LOGLOG comme la classe de langues qui peut être calculée dans l'espace O (loglog n) par une machine de Turing déterministe (avec un accès bidirectionnel à l'entrée). De même, définissez NLOGLOG comme la classe de langues qui peut être calculée dans l'espace O (log log n) par une machine de Turing non déterministe (avec un accès bidirectionnel à l'entrée). Ne sait-on pas vraiment que ces classes diffèrent?

Je ne pouvais trouver que des enquêtes plus anciennes et un théorème qui, s'ils étaient égaux, alors L = NL (qui n'est pas seulement un argument de remplissage trivial!), Mais je pense que séparer ces classes ne peut pas être si difficile. Bien sûr, je peux me tromper complètement, mais si chaque deuxième bit de l'entrée est les nombres de 1 à n dans l'ordre croissant en binaire, séparés par certains symboles, alors les machines peuvent déjà apprendre le journal de bord n ​​et avec chaque deuxième bit, nous pouvons saisir un problème qui peut tromper une machine déterministe mais pas non déterministe. Je ne vois pas encore exactement comment cela pourrait être fait, mais cela ressemble à une approche possible, car avec cette astuce, nous pouvons essentiellement saisir un arbre binaire de profondeur n avec sa structure au lieu de la bande linéaire habituelle.

L' entrée dans le zoo de la complexité est étonnamment détaillée; il prétend que NLOGLOG = co-NLOGLOG dans le document

Calculs non déterministes dans l'espace sublogarithmique et la constructibilité de l'espace , Viliam Geffert, SIAM Journal on Computing, 1991.

Mais après une brève lecture, je ne vois aucune allégation sur le fait que NLOGLOG est fermé sous complément; un examen plus approfondi est peut-être nécessaire. Et le principal résultat qu'ils ont est qu'il n'y a pas de fonctions monotones non déterministes non bornées et entièrement constructibles augmentant pour . On sait que si de telles fonctions existent, alors$s(n)$$s(n) = o(\log n)$

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

Et dans la conclusion, l'auteur a affirmé que "... ce principal problème de séparation reste ouvert ".

Comme l'a dit @chazisop, les relations de ces classes de complexité de bas niveau dépendent des modèles, et il est indiqué dans l'entrée du zoo que

"Il existe plusieurs définitions possibles de cette classe; la plus courante est la classe de langages qui peut être calculée dans l'espace O (log log n) par une machine de Turing déterministe avec un accès bidirectionnel à l'entrée."

Ce qui coïncide avec votre définition et aussi celle du papier.