Pourquoi est-on exige souvent constructibilité de l'espace dans le théorème de Savitch?

Question

Quand le fameux théorème de Savitch est dit, on voit souvent l'exigence que $ S (n) $ soit un espace constructible (Fait intéressant, il est omis dans Wikipedia). Ma question est simple: Pourquoi avons-nous besoin de cela? Je comprends l'exigence de $ S (n) étant $ en $ \ Omega (\ log n) $, ce qui ressort de la preuve. Mais aucune preuve que je l'ai vu jusqu'à présent utilise explicitement que $ S (n) $ est un espace constructible.

Mon explication: pour appeler la procédure REACH (ou PATH ou tout ce que vous voulez l'appeler), les derniers besoins des paramètres à « énoncés », et pour ne pas laisser nos limites spatiales de S (n) pour un appel, il ne faut pas avoir besoin de plus de $ S (n) $ espace pour écrire.

Answer 1

Je crois que votre explication est correcte. Le sous-programme st-REACH obtient $ (s, t, \ ell) $ en entrée, et trouve ou non $ t $ est accessible à partir de $ par $ \ ell étapes $. $ S $ et $ t $ seront les configurations initiales et finales, et $ \ ell = 2 ^ {O (s (n))} $, la limite supérieure du nombre de configurations différentes.

Afin de mettre $ \ ell un $ doit être en mesure de calculer de $ (n) $ (ou plutôt 2 $ ^ {O (s (n))} $). Si ce processus prend plus de $ O (s ^ 2 (n)) $ espace, la machine entière aura plus d'espace que le permis. Il est possible que même O $ (s ^ 2 (n)) $ est trop à cause de l'appel récursif à st-REACH (est-il une autre raison possible?), Mais je n'ai pas vérifié cela.

Answer 2

Ceci est bien élaboré dans la théorie de Dexter Kozen du manuel de calcul, dans le chapitre 2.

de Savitch théorème (théorème 1 dans son article) dit: si $ S (n) \ ge \ log n $, puis le texte $ \ {NSPACE} (S (n)) \ subseteq \ texte {DSPACE} (S ( n) ^ 2) $. L'espace-constructibilité semble souvent être pris dans une preuve, mais cette exigence peut être retirée en redémarrant la recherche d'un espace fixe lié qui est autorisé à augmenter à chaque tentative.

La confusion se pose peut-être parce que le papier Savitch originale est en grande partie à examiner si $ \ texte {} NSPACE (S (n)) \ not \ subseteq \ texte {} DSPACE (S (n)) $. Il passe donc beaucoup d'efforts sur les fonctions-espace constructible, en raison de l'observation suivante du papier:

Il est naturel de se demander s'il y a une fonction de stockage dont les classes de complexité déterministe et non déterministes sont égaux. La réponse a été donnée par Manuel Blum et est « oui ». Blum a montré qu'il y a des fonctions arbitrairement grand de stockage L (n) de telle sorte qu'un ensemble est accepté dans le stockage déterministe L (n) si, et seulement si, il est accepté à l'intérieur de stockage non déterministe L (n). Ces fonctions L (n) ne sont pas, cependant, « bien comportés » et le théorème 3 ne concerne pas les.

(ici "bien comportés" fait référence aux fonctions espace constructible, appelé mesurable par Savitch.)