Justification de log f dans le théorème de la hiérarchie DTIME

Si nous regardons le théorème de la hiérarchie DTIME, nous avons un journal en raison de la surcharge dans la simulation d'une machine de Turing déterministe par une machine universelle:

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

Nous n'avons pas ce genre de frais généraux pour NTIME de DSPACE. Une justification de base vient des détails de la preuve en considérant la différence entre les simulateurs.

Ma question est la suivante: sans considérer le détail de la preuve du théorème de la hiérarchie DTIME, y a-t-il une justification de ce log ou cela pourrait être juste une conséquence de la preuve et il serait raisonnable d'imaginer que si $f = o(g)$ puis

$DTIME(f) \subsetneq DTIME(g)$

À mon avis, considérer que l'explication de la simulation est une bonne justification devrait être lui-même justifié en prouvant que si nous avions un meilleur résultat, nous pourrions créer une meilleure simulation.

Le théorème de la hiérarchie du temps est le sujet de mon projet de diplôme, peut-être que vous voulez voir les commentaires sur ma question Limites inférieures et séparation des classes .

En repensant à cette question et à la façon dont elle se rapporte à ce que vous demandez, j'ai eu une idée qui pourrait montrer que les frais généraux de simulation TM multi-bande à bande unique nécessaires à la preuve du théorème ne peuvent pas être améliorés. Ainsi, une autre approche est nécessaire si nous voulons améliorer ce résultat.

EDIT: Cette preuve est incorrecte, voir les commentaires ci-dessous pour la raison exacte. J'édite actuellement la réponse pour refléter cela.

Soit la langue .{ 0 k 1 k | k ≥ 0 $A$$\{ 0^{k}1^{k}| k \geq 0 \}$

Sur une seule machine à bande, il existe un algorithme (vous pouvez trouver les détails de cet algorithme au chapitre 7.1.2 du livre de Sipser "Introduction à la théorie du calcul). Dans la même référence, vous pouvez voir qu'une langue est en o (n \ log n) si et seulement si elle est régulière. Kaveh fournit également les documents originaux pour cette affirmation dans la question liée ci-dessus.$O(n \log n)$

Dans les commentaires de ma question, Ryan Williams illustre un algorithme pour le même problème, en utilisant une TM à 2 bandes.$O(n)$

Supposons maintenant qu'il existe une technique pour simuler une MT multitape en une seule bande TM qui a un temps d'exécution de , où est le temps d'exécution de la TM simulée . En l'appliquant à la machine illustrée par Ryan, nous obtiendrions une seule bande TM qui s'exécuterait en . Par conséquent, est régulier, ce qui est une contradiction. Ainsi, nous concluons qu'une surcharge de est la meilleure que nous puissions faire lors de la simulation de machines à bandes multiples avec des machines à bande uniques.T ( n ) o ( n log n ) A log T ( n $o( T(n) \log T(n) )$$T(n)$$o( n \log n)$$A$$\log T(n)$

Je me rends compte que c'est une déclaration forte, donc je peux me tromper dans mon interprétation.

Même s'il existe une technique qui permet d'améliorer ce résultat, je pense qu'il n'est pas possible de faire correspondre le résultat pour ou . Mon intuition dérive du fait suivant:S P A C $NTIME$$SPACE$

Il existe un résultat très connu qui indique . Sous l'hypothèse que je crois que ce résultat est amélioré en , pour tout .Ainsi, une très petite classe non déterministe est beaucoup plus puissante que tout déterministe . Donc, étant donné la puissance d'un temps non déterministe d'une ressource, je m'attendrais à ce qu'une plus grande quantité de temps déterministe soit nécessaire pour rendre une MT plus puissante pour compenser la puissance du non-déterminisme.P ≠ N $DTIME(n) \neq NTIME(n)$$P \neq NP$$DTIME(n^{k}) \neq NTIME(n)$$k$

Pour les TM n-tape, un résultat de hiérarchie temporelle serré similaire au théorème de la hiérarchie spatiale est prouvé par Furer en 1982. Le facteur n'est pas nécessaire.$\lg$

Le facteur pour le théorème de la hiérarchie temporelle indiqué dans votre article ne concerne que les MT à bande unique. Sauf si vous êtes très attaché au modèle à bande unique pour une raison quelconque, il n'y a pas de différence entre l'espace et le temps en ce qui concerne les théorèmes de hiérarchie.$\lg$

Il existe des raisons et des arguments pour utiliser des MT à bande unique pour définir des classes de complexité temporelle, mais l'utilisation de MT à bande unique pour définir des classes de complexité n'est pas universelle, par exemple, voir Lance Fortnow et Rahul Santhanam [2007] où ils utilisent plusieurs bandes. MT.

La référence d'origine pour le théorème de la hiérarchie temporelle est Hennie et Stearns [1966]. Ils prouvent le théorème des machines à deux bandes. La théorie classique de la récursivité d'Odifreddi les cite ainsi que Hartmanis [1968] et décrit une preuve qui ressemble à celle du livre de Sipser.

Cependant, la preuve des MT à bande unique dans l'article de Hartmanis n'utilise pas simplement la simulation. Il distinguait deux cas: 1. le temps d'exécution étant et 2. le temps d'exécution étant .$\Omega(n^2)$$o(n^2)$

1. Pour le premier cas, il utilise une simulation, et il semble que l'on puisse se débarrasser du facteur si les simulations peuvent être effectuées plus efficacement.$\lg$

2. Pour le deuxième cas, le papier donne directement une langue pour la séparation et n'utilise pas du tout la simulation. Cela utilise des propriétés particulières des MT à bande unique avec une durée de fonctionnement sub-quadratique.

Il convient de noter que les MT à bande unique avec le temps ne sont pas aussi robustes et qu'il existe des limites inférieures quadratiques (par exemple pour les Palindroms) sur les MT à bande unique alors qu'une MT à deux bandes peut résoudre ces problèmes en temps linéaire.$o(n^2)$

Comme je l'ai dit ci-dessus, à moins que vous ne soyez engagé dans le modèle TM à bande unique pour une raison quelconque, même lorsque le temps est sub-quadratique, il n'y a pas de vide à combler, le théorème de la hiérarchie temporelle est aussi serré que possible.

PS: si nous utilisons des MT à bandes multiples, c'est-à-dire qu'une machine Turing de la classe peut avoir un nombre fixe mais arbitraire de bandes, le résultat de Fürer ne s'applique pas.

1. Martin Fürer, " La hiérarchie temporelle déterministe serrée ", 1982
2. Piergiorgio Odifreddi, "Théorie classique de la récursivité", vol. II, 1999 (page 84)
3. Juris Hartmanis, " Complexité computationnelle des calculs de machine de Turing à une bande ", 1968
4. FC Hennie et RE Stearns, " Simulation à deux bandes de machines de Turing à bandes multiples ", 1966
5. L'article de Lance Fortnow et Rahul Santhanam " Time Hierarchies: A Survey ", 2007

Pour un nombre fixe de bandes supérieur à un, ) pour constructible dans le temps . Le surcoût logarithmique provient du théorème de réduction de bande, où un nombre quelconque de bandes peuvent être converties en deux bandes (ou même juste une seule bande et une pile et avec juste un mouvement inconscient).$\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$$f$

Si le nombre de bandes n'est pas fixe, nous n'avons pas vraiment de technique pour prouver de manière constructive sans passer par le théorème de réduction de bande. Il est plausible que pour chaque , les machines à bandes ne puissent pas être simulées par des machines à bandes sans surcharge logarithmique.$\mathrm{DTime}(g) ⊊ \mathrm{DTime}(f)$$k$$k+1$$k$

Cependant, cela ne signifie pas que le théorème de la hiérarchie temporelle ne peut pas être amélioré, ou que échoue.$\mathrm{DTime}(o(f)) ⊊ \mathrm{DTime}(O(f))$

En fait, nous avons déjà les éléments suivants.

Théorème: Pour tout et tout de la forme ( et rationnel; ou ), .$ε>0$$f$$n^a (\log n)^b$$a$$b$$a>1$$a=1∧b≥0$$\mathrm{DTime}(O(f /(\log f)^ε) ⊊ \mathrm{DTime}(O(f))$

Preuve: si chaque langue avec un algorithme de décision peut être décidée en temps , alors en complétant l'entrée, chaque langue avec un algorithme de décision peut être décidé en temps (où est fixé ), et donc pour chaque constante , , contredisant le théorème de la hiérarchie temporelle.$O(f)$$O(f / (\log f)^ε)$$O(f(n) (\log f(n))^{kε})$$O(f(n) \, (\log f(n))^{(k-1)ε})$$k≥0$$c≥0$$\mathrm{DTime}(O(f(n) (\log f(n))^c)) = \mathrm{DTime}(O(f(n)))$

Cependant, cette preuve non constructive a trois limites:
* La preuve nécessite que soit bien comporté (non seulement constructible dans le temps, mais aussi dans un certain sens continu). * Nous ne connaissons pas de langage particulier qui se trouve dans mais pas dans . Pour un suffisamment grand , la simulation des machines de Turing à bande n'est pas dans , mais nous n'avons pas exclu que même pour et , le moins tel soit> BB (BB (1000)) où BB est la fonction de castor occupé. * Nous ne savons pas que l'inclusion est robuste.$f$
$\mathrm{DTime}(O(f))$$\mathrm{DTime}(O(f/(\log f)^ε)$$k$$k$$\mathrm{DTime}(O(f/(\log f)^ε)$$ε=1$$f(n)=n^2$$k$
$\mathrm{DTime}(O(f/(\log f)^ε)$ échouera pour certaines entrées, mais nous n'avons pas prouvé qu'il échoue pour certaines entrées pour toutes les tailles d'entrée, mais en nombre fini (bien que ce soit très surprenant) si ce n'est pas le cas).