Problèmes complets pour $ DSPACE (\ log (n) ^ k) $

Question

Nous savons que le $ polyl $ -hierarchy n'a pas de problèmes complets, car il serait incompatible avec le théorème de hiérarchie spatiale. Mais: Y at-il des problèmes complets pour chaque niveau de cette hiérarchie

?

Pour être précis: Est-ce que DSPACE classe $ (\ log (n) ^ k) $ ont des problèmes complets sous -réductions $ L $ pour chaque k $> 0 $

Answer 1

Une preuve standard du théorème de hiérarchie spatiale est basée sur la simulation spatiale efficace des machines de Turing. Si je ne me trompe pas, cette simulation implique que pour chaque fonction constructible espace f : N ? N, le problème suivant est DSPACE ( f ( n )) (où n est la longueur d'entrée):

  

Etant donné un codage d'une machine de Turing déterministe M avec une bande d'entrée en lecture seule et une bande de travail de lecture-écriture d'un alphabet de travail fixe (tel que {0, 1, vide}), une chaîne x , et une chaîne de caractères de pointage 1 ^t , décider si M arrêts sur chaîne d'entrée x avant d'utiliser plus de f ( t ) l'espace de travail.

Ce problème est DSPACE ( f ( n )) - log-espace beaucoup-un sous réductibilité dur. Voici une preuve en cas de f ( n ) = lg ^k n . Pour chaque langue L ?DSPACE (log ^k n ), il y a une machine de Turing M (de la forme indiquée ci-dessus) qui accepte l c lg ^k n espace pour certains c ?N. Modifier M M 'de sorte que lorsque M rebuts, M ' entre dans une boucle infinie à la place. Ensuite, étant donné une chaîne d'entrée x , laissez t = | x | ^c , et on génère l'instance ( M ', x , 1 ^t ) du problème ci-dessus. (Je pense que la seule partie non négligeable est un peu que nous ne pouvons pas régler t = | x |.)

Par conséquent, ce problème est DSPACE ( f ( n )) -. Log-espace beaucoup-un réductibilité sous complet

Answer 2

Juste un commentaire exetended.

Dans le document « Le problème pour Emptiness intersections des langues régulière » il est montré que la décision du vide de l'intersection des langues reconnues par $ G (n) $ DFA est complet pour NSPACE $ (g (n) \ log {n}) $; en particulier le vide de l'intersection des langues reconnues par $ \ log ^ {k-1} {n} $ DFA est complet pour $ NSPACE (log ^ {k} {n}) $, $ k \ geq 1 $.

Mais il semble que le même résultat ne peut pas se limiter à DPSACE si l'on considère l'intersection vide des langues reconnues par $ g (n) $ Tally-DFA (DFA avec un seul symbole dans l'alphabet).

Toutefois $ \ emptyset = \ bigcap ^ k DFA_ {lin} $ est complet pour DSPACE $ (\ log {n}) $ pour chaque $ k $.