NTIME (f) sous-ensemble de DSPACE (f)

Comme l'indique la question, comment prouver que ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Quelqu'un peut-il m'indiquer une preuve ou la décrire ici? Merci!

complexity-theory time-complexity space-complexity gdiazc
la source

Je suppose qu'il y en a plusieurs. des constantes qui s'y cachent. Vous pouvez prouver que

. Énumérez simplement toutes les suppositions non déterministes possibles de l'algorithme et exécutez votre algorithme avec ces suppositions. Acceptez si l'une des suppositions mène à un état d'acceptation.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Igor Shinkar

Pourquoi ne pas en faire une réponse?

Yuval Filmus

@IgorShinkar Il existe différents résultats, tels que le théorème d'accélération linéaire et le théorème de compression de bande qui disent que vous pouvez vous débarrasser de ces constantes dans "la plupart" des circonstances. L'accélération linéaire dit que

pour tout

; la compression sur bande indique que

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

, à nouveau pour tout

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

David Richerby

Réponses:

Voici une version étendue du commentaire d'Igor Shinkar. La manière la plus simple de simuler une machine non déterministe fonctionnant dans le temps et l'espace utilise l' espace . Nous énumérons tous les lancements de pièces possibles, en simulant la machine d'origine sur chacun d'eux; cela nécessite un espace pour stocker les lancers de pièces, et $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ espace pour simuler la machine réelle. Il y a une légère difficulté ici: lorsque les lancements de pièces sont "lus" par la machine (d'origine), nous devons marquer d'une manière ou d'une autre où nous en sommes dans la séquence des lancements de pièces; nous pouvons utiliser un bit supplémentaire par tirage au sort. Il est probablement possible de l'optimiser encore plus. $s(n)$

Si nous sommes prudents, nous pourrons peut-être obtenir quelque chose d'encore mieux, car à chaque exécution du programme, le nombre total de lancers de pièces et l'espace total utilisé s'ajoutent à au plus . Je soupçonne qu'il est possible d'exécuter la simulation dans l' espace . Peut-être que nous devrons supposer quelque chose comme pour cela. $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Comme Igor le mentionne, les classes limitées aux ressources ne sont généralement définies que "jusqu'au grand O", de sorte que le résultat, qui utilise l'espace , est toujours dans . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
la source