DTIME - DTIME

Dans la théorie de la complexité computationnelle , DTIME (ou TIME ) est la ressource de calcul du temps de calcul pour une machine de Turing déterministe . Il représente le temps (ou le nombre d'étapes de calcul) qu'un ordinateur physique "normal" prendrait pour résoudre un certain problème de calcul à l' aide d'un certain algorithme . C'est l'une des ressources de complexité les mieux étudiées, car elle correspond si étroitement à une ressource importante du monde réel (le temps qu'il faut à un ordinateur pour résoudre un problème).

La ressource DTIME permet de définir des classes de complexité , ensembles de l'ensemble des problèmes de décision pouvant être résolus avec un certain temps de calcul. Si un problème de taille d'entrée n peut être résolu dans , nous avons une classe de complexité (ou ). Il n'y a aucune restriction sur la quantité d' espace mémoire utilisée, mais il peut y avoir des restrictions sur d'autres ressources de complexité (comme alternation ). ${\style d'affichage O(f(n))}$${\displaystyle {\mathsf {DTIME}}(f(n))}$${\displaystyle {\mathsf {TIME}}(f(n))}$

Classes de complexité dans DTIME

De nombreuses classes de complexité importantes sont définies en termes de DTIME , contenant tous les problèmes qui peuvent être résolus dans un certain laps de temps déterministe. Toute fonction de complexité appropriée peut être utilisée pour définir une classe de complexité, mais seules certaines classes sont utiles à étudier. En général, nous souhaitons que nos classes de complexité soient robustes contre les changements dans le modèle de calcul et soient fermées sous la composition de sous-programmes.

DTIME satisfait le théorème de la hiérarchie temporelle , ce qui signifie que des quantités de temps asymptotiquement plus grandes créent toujours des ensembles de problèmes strictement plus grands.

La classe de complexité bien connue P comprend tous les problèmes qui peuvent être résolus dans une quantité polynomiale de DTIME . Il peut être défini formellement comme :

${\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$

P est la plus petite classe robuste qui inclut des problèmes en temps linéaire (AMS 2004, Lecture 2.2, p. 20). P est l'une des plus grandes classes de complexité considérée comme « informatiquement faisable ». ${\displaystyle {\mathsf {DTIME}}\left(n\right)}$

Une classe beaucoup plus large utilisant le temps déterministe est EXPTIME , qui contient tous les problèmes pouvant être résolus à l'aide d'une machine déterministe en temps exponentiel . Formellement, nous avons

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}$

Des classes de complexité plus grandes peuvent être définies de la même manière. En raison du théorème de la hiérarchie temporelle, ces classes forment une hiérarchie stricte ; nous le savons , et ainsi de suite. ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$

Modèle de machine

Le modèle de machine exact utilisé pour définir DTIME peut varier sans affecter la puissance de la ressource. Les résultats de la littérature utilisent souvent des machines de Turing multibandes , en particulier lorsqu'il s'agit de classes de temps très réduites. En particulier, une machine de Turing déterministe multibande ne peut jamais fournir plus qu'une accélération quadratique du temps par rapport à une machine monobande.

Les constantes multiplicatives dans la quantité de temps utilisé ne modifient pas la puissance des classes DTIME ; une accélération multiplicative constante peut toujours être obtenue en augmentant le nombre d'états dans le contrôle d'état fini. Dans l'énoncé de Papadimitriou, pour une langue L ,

Laissez . Ensuite, pour tout , , où .${\displaystyle L\in {\mathsf {DTIME}}(f(n))}$${\displaystyle \epsilon >0}$${\displaystyle L\in {\mathsf {DTIME}}(f'(n))}$${\style d'affichage f'(n)=\epsilon f(n)+n+2}$

Généralisations

En utilisant un modèle autre qu'une machine de Turing déterministe, il existe diverses généralisations et restrictions de DTIME. Par exemple, si nous utilisons une machine de Turing non déterministe , nous avons la ressource NTIME . La relation entre les pouvoirs expressifs de DTIME et d'autres ressources de calcul est très mal comprise. L'un des rares résultats connus est

${\displaystyle {\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))}$

pour les machines multibandes. Celui-ci a été étendu à

${\displaystyle {\mathsf {DTIME}}(O(n{\sqrt {\log ^{*}n}}))\neq {\mathsf {NTIME}}(O(n{\sqrt {\log ^{ *}n}}))}$

par Santhanam.

Si nous utilisons une machine de Turing alternative , nous avons la ressource ATIME.

Les références

• Société mathématique américaine (2004). Rudich, Steven et Avi Wigderson (éd.). Théorie de la complexité computationnelle . Société mathématique américaine et Institut d'études avancées . ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Complexité computationnelle . Reading, Massachusetts : Addison-Wesley. ISBN 0-201-53082-1.