Spazio complessità di sotto di $ \ log \ log $

Question

Mostra che per $ l (n) = \ log \ log n $, vale che $ \ text {DSPACE} (o (l)) = \ text {DSPACE} (O (1)) $.

E 'ben noto infatti in Space Complessità, ma come per mostrare in modo esplicito?

Answer 1

Così qui è l'idea principale dietro questo fatto. Indichiamo con $ C $ ogni possibile configurazione di $ l (n) $ - spazio delimitato TM. Si noti che $ | C | \ le 2 ^ {c \ cdot l (n)} $, dove $ c $ è una costante a seconda $ M $.

Si assume che il nastro di ingresso è un nastro a due vie. Sia $ w $ essere una parola di dimensioni $ n $, tale che per tutte le parole più piccoli $ u $ abbiamo $ l (w)> l (u) $. Quando la testa si sposta dalla posizione $ i $ posizionarla $ i + 1 $ sul nastro di ingresso, o viceversa, registriamo la configurazione corrente del calcolo nella attraversando sequenza $ C_I $. Supponiamo di avere $ i \ neq j $ con $ C_I = C_J $. Poi definiamo da $ w '$ parola ottenuta da $ w $ cancellando tutto tra il numero di caratteri $ i $ e $ j $. Osserviamo che $ w '$ è una parola più corta che utilizza la stessa quantità di spazio. La contraddizione, non esiste $ w $.

Se $ l (n) \ O (\ log \ log n) $ allora avete $ o (\ log n) $ configurazioni e $ O (n) $ sequenze di attraversamento. Quindi due sequenze di attraversamento sono uguali.

Si noti che se il nastro di ingresso è 1 a senso unico, quindi anche con $ o (\ log n) $ spazio si sono condannati.

Answer 2

La (credo) la prova originale è di Hartmanis, Lewis & Stearns , comodamente disponibili gratuitamente:.)

La mia comprensione approssimativa di esso è che va via l'equivalenza alla classe dei linguaggi regolari nel senso che hai solo bisogno di una quantità costante di spazio per decidere un linguaggio regolare (basta qualunque stato che è fino a, in fondo), in modo da 'ri decidibile a $ DSPACE (O (1)) $, ma se si vuole decidere nulla non regolare , allora avete bisogno di $ \ Omega (\ log \ log n) $ spazio, quindi non c'è un "vuoto" gap, anche con quel po 'di spazio ($ o (\ log \ log n) $), è così piccolo che non si può fare nulla di nuovo con esso.