Problemas completas para DSPACE $ (\ log (n) ^ k) $

Question

Sabemos que el polil $ $ -hierarchy no tiene problemas completos, ya que entraría en conflicto con el teorema de la jerarquía espacial. Pero: ¿Hay problemas completas para cada nivel de esta jerarquía

?

Para ser precisos:? ¿La clase $ DSPACE (\ log (n) ^ k) $ tienen problemas completos de menos de $ L $ -reductions para cada k $> $ 0

Answer 1

Una prueba estándar del teorema de la jerarquía espacial se basa en la simulación eficiente del espacio de máquinas de Turing. Si no me equivoco, esta simulación implica que para cada función en el espacio construible f : N ? N, el siguiente problema es en DSPACE ( f ( n )) (donde n es la longitud de entrada):

Dada una codificación de una máquina de Turing determinista M con una cinta de sólo lectura de entrada y una cinta de trabajo de lectura-escritura con un alfabeto de trabajo fija (tales como {0, 1, espacio en blanco}), una cadena x , y una cadena tally 1 ^t , decidir si M se detiene en cadena de entrada x antes de usar más de f ( t ) espacio de trabajo.

Este problema es DSPACE ( f ( n )) - duro bajo log-espacio mucho-uno reducibilidad. Aquí es una prueba en el caso de f ( n ) = lg ^k n . Para cada idioma L ?DSPACE (log ^k n ), hay una máquina de Turing M (de la forma se ha indicado anteriormente), que acepta L en c lg ^k n espacio para algunos c ?N. Modificar M a M 'de modo que cuando M rechazos, M ' entra en un bucle infinito en su lugar. A continuación, dada una cadena de entrada x , dejo t = | x | ^c , y generamos la instancia ( M ', x , 1 ^t ) del problema anterior. (Creo que la parte no trivial es sólo un poco que no podemos establecer t = | x |.)

Por lo tanto este problema es DSPACE ( f ( n )) -. Completo bajo log-espacio mucho-uno reducibilidad

Answer 2

Sólo un comentario exetended.

En el documento " el vacío problema de las intersecciones de regular de idiomas " Es mostraron que decidir el vacío de la intersección de las lenguas reconocido por $ G (n) $ DFA es completa por $ NSPACE (g (n) \ log {n}) $; en particular, el vacío de la intersección de las lenguas reconocidas por $ \ log ^ {k-1} {n} $ DFA es completa por $ NSPACE (log ^ {k} {n}) $, $ k \ geq 1 $.

Sin embargo, parece que el mismo resultado no puede limitarse a DPSACE si tenemos en cuenta la intersección vacío de idiomas reconocidos por $ g (n) $ Cuenta-DFA (DFA con sólo un símbolo en el alfabeto).

Sin embargo $ \ emptyset = \ bigcap ^ k DFA_ {lin} $ es completa por $ DSPACE (\ log {n}) $ por cada $ k $.