la complexité de l'espace ci-dessous $ \ log \ log $

Question

Montrer que pour $ l (n) = \ log \ log n $, il estime que le texte $ \ {dspace} (o (l)) = \ texte {DSPACE} (O (1)) $.

Il est un fait bien connu dans l'espace complexité, mais comment le montrer explicitement?

Answer 1

Voici donc l'idée principale derrière ce fait. Appelons $ C $ toutes les configurations possibles de $ l (n) de $ - espace délimité TM. Notez que $ | C | \ le 2 ^ {c \ cdot l (n)} $, où $ c $ est une constante en fonction de $ M $.

Nous supposons que la bande d'entrée est une bande à double sens. Soit $ w $ un mot de taille $ n $, de sorte que pour tous les petits mots $ u $ que nous avons $ l (w)> l (u) $. Lorsque la tête se déplace de la position $ i $ à la position i + 1 $ $ sur la bande d'entrée, ou vice versa, on enregistre la configuration actuelle du calcul de la séquence traversant $ C_i $. Supposons que nous ayons $ i \ j NEQ $ avec $ C_i = $ C_J. Ensuite, nous définissons comme $ w '$ le mot obtenu à partir de $ w $ en supprimant tout entre le nombre de caractères $ i $ et $ j $. Nous observons que $ w '$ est un mot plus court qui utilise la même quantité d'espace. Contradiction, il n'y a pas $ w $.

Si $ l (n) \ o dans (\ log \ log n) $, alors vous avez $ o (\ log n) $ configurations et o $ (n) $ séquences de passage. Ainsi, deux séquences de passage sont les mêmes.

Notez que si votre bande d'entrée est de 1 à sens unique, alors même avec $ o (\ log n) $ l'espace que vous êtes condamné.

Answer 2

(je pense) la preuve d'origine est par Hartmanis, Lewis & Stearns , facilement disponible gratuitement.)

Ma compréhension approximative de c'est qu'il passe par équivalence à la classe des langues régulières dans le sens où vous avez seulement besoin d'une quantité constante d'espace pour décider d'une langue régulière (juste quelque état qu'il est à, au fond), de sorte qu'ils « re décidable en $ DSPACE (O (1)) $, mais si vous voulez décider quoi que ce soit non régulier , alors vous avez besoin $ \ Omega (\ log \ n log) $ l'espace, donc il y a un « vide » écart, même avec ce petit supplément d'espace ($ o (\ log \ log n) $), il est si petit que vous ne pouvez pas faire quelque chose de nouveau avec elle.