Est-ce que $ \ mathsf {} NSPACE (f (n)) = \ {mathsf coNSPACE} (f (n)) $ pour tenir $ f (n) <\ log (n) $?

Question

On sait que pour $ f (n) \ geq \ n log $, $ \ mathsf {NSPACE} (f (n)) = \ mathsf {coNSPACE} (f (n)) $.

Et si $ f (n) <\ log n $? Sont-ils égaux aussi?

Answer 1

théorème fonctionne Immerman-Szelepcsényi en réduction logarithmique . classes d'espace Sublogarithmic ont des réductions. Les mémoires de traduction qui travaillent dans espace sublogarithmic ne peut même enregistrer la longueur de l'entrée . Il a été démontré que la hiérarchie de l'espace pour tout sublogarithmic lié O (log n de journal) - o (log n) est infinie. Vous pouvez le trouver dans les références suivantes:

V. Geffert. Sublogarithmic s2-espace est pas fermé en complément et une autre séparation résultats . Informatique théorique et applications, 27: 349-366., 1993

M. Liskiewicz et R. Reischuk. La séparation des niveaux inférieurs de l'espace sublogarithmic hiérarchie . Dans Actes du Colloque sur les aspects théoriques de l'informatique, pages 6-27, 1993.

B. von Braunmuhl " pour les machines à deux Alternance sens avec l'espace sublogarithmic ". Dans Actes du colloque sur les aspects théoriques de l'informatique, pages 5-15, 1993.

Le document Le monde de complexité ci-dessous l'espace logarithmique par M. Liskiewicz et R. Reischuk contient une excellente récapitulation de l'espace sublogarithmic.