DTIME (Complexitat)

En la Teoria de complexitat computacional, la família DTIME (de vegades simplement TIME) és el recurs de computació en temps de computació per una màquina de Turing determinista. Representa la quantitat de temps (o nombre de cicles de computació) que un computador "normal" prendrà per resoldre un cert problema computacional usant un cert algorisme. És un dels recursos més ben estudiats perquè es correspon amb un recurs real força important com és el temps de còmput.

Aquest recurs s'utilitza per definir classes de complexitat, conjunts de problemes de decisió que es poden resoldre usant un cert temps de computació. Si un problema amb una entrada de mida n es pot solucionar en O(f(n)), es te la classe de complexitat DTIME(f(n)). No hi ha restricció en la quantitat de memòria utilitzada, però pot haver-hi restriccions en d'altres recursos.

Classes de complexitat dins de DTIME

DTIME satisfà el teorema de la jerarquia temporal, que significa que temps asimptoticament més llargs sempre creen conjunt de problemes més llargs.

La classe de complexitat P es pot definir com:

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

P és la classe més petita que pot contenir els problemes de temps lineal (DTIME(n)) alhora que P inclou el conjunt de problemes considerats tractables. Una classe molt més gran de problemes, que conté tots els problemes que es poden resoldre usant una màquina de Turing determinista en temps exponencial (EXPTIME). Formalment es defineix com:

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

Es poden definir classes de complexitat més grans de forma similar. Pel teorema de la jerarquia del temps, aquestes classes formen una jerarquia estricta. Per això se sap que ${\displaystyle \mathrm {P} \subsetneq \mathrm {EXPTIME} }$.

Generalitzacions

Usant una màquina diferent a la màquina de Turing determinista, es poden fer diverses generalitzacions de DTIME. Per exemple, usant una màquina de Turing no determinista, es té el recurs NTIME. La relació entre aquests dos recursos és poc coneguda, un dels pocs resultat que es te és:

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

per màquines amb múltiples cintes. Es va poder estendre aquest resultat a:

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

Si s'usa una màquina de Turing alternant, s'obté el recurs ATIME.