Problemi completi per $ DSPACE (\ log (n) ^ k) $

Question

Sappiamo che il $ Polyl $ -hierarchy non ha problemi di completi, in quanto sarebbe in conflitto con il teorema di gerarchia di spazio. Ma: Ci sono problemi complete per ogni livello di questa gerarchia

?

Per essere precisi:? Fa la classe $ DSPACE (\ log (n) ^ k) $ avere problemi completi sotto $ L $ -reductions per ogni $ k> 0 $

Answer 1

Una prova standard del teorema di gerarchia di spazio si basa sulla simulazione spazio-efficiente di macchine di Turing. Se non mi sbaglio, questa simulazione implica che per ogni funzione spazio-costruibile f : N ? N, il seguente problema è nella DSPACE ( f ( n )) (dove n è la lunghezza ingresso):

Dato una codifica di una macchina di Turing deterministica M con un nastro di sola lettura ingresso e un nastro di lavoro di lettura-scrittura con un alfabeto lavoro fissa (come {0, 1, vuoto}), una stringa x , e una stringa tally 1 ^t , decidere se M arresta sulla stringa di input x prima di utilizzare più di f ( t ) lo spazio di lavoro.

Questo problema è DSPACE ( f ( n )) - sotto duro log-spazio molti-uno riducibilità. Qui è una prova nel caso di f ( n ) = lg ^k n . Per ogni lingua L ?DSPACE (log ^k n ), c'è una macchina di Turing M (di forma indicato sopra) che accetta L c lg ^k n lo spazio per un po 'di c ?N. Modifica M M 'in modo che quando M scarti, M ' entra in un ciclo infinito invece. Poi dato una stringa di input x , lascio t = | x | ^c , e generiamo l'istanza ( M ', x , 1 ^t ) del problema di cui sopra. (Credo che la parte solo leggermente non banale è che non siamo in grado di impostare t = | x |.)

Quindi questo problema è DSPACE ( f ( n )) -. Completo sotto log-spazio molti-uno riducibilità

Answer 2

Solo un commento poggia su due sole.

Nel documento " il vuoto problema per intersezioni di regolare lingue " E 'dimostrato che decidere il vuoto dell'intersezione dei linguaggi riconosciuto da $ G (n) $ DFA è completa a $ nSpazio (g (n) \ log {n}) $; in particolare il vuoto dell'intersezione dei linguaggi riconosciuti da $ \ log ^ {k-1} {n} $ DFA è completo per $ nSpazio (log ^ {k} {n}) $, $ k \ geq 1 $.

Ma sembra che lo stesso risultato non può essere limitato a DPSACE se consideriamo l'intersezione vuoto di lingue riconosciute da $ g (n) $ Tally-DFA (DFA con un solo simbolo in alfabeto).

Tuttavia $ \ emptyset = \ bigcap ^ k DFA_ {lin} $ è completo per $ DSPACE (\ log {n}) $ per ogni $ k $.