DTIME

În teoria complexității , DTIME (sau TIME ) desemnează o familie de clase de complexitate caracterizate prin complexitatea lor de timp pe o mașină determinantă de Turing .

Mai precis, este clasa problemelor de decizie care, pentru o intrare de dimensiune , pot fi rezolvate în timp de o mașinărie Turing deterministă. DTEuME(f(nu)){\ displaystyle {\ mathsf {DTIME}} (f (n))}nu{\ displaystyle n}O(f(nu)){\ displaystyle {\ mathcal {O}} (f (n))}

Definiții

Clasa P a problemelor de decizie care pot fi decise de o mașină Turing deterministă în timp polinomial cu privire la dimensiunea intrării poate fi definită ca:

P=⋃k∈NUDTEuME(nuk){\ displaystyle {\ mathsf {P}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} (n ^ {k})}

De asemenea, EXPTIME clasa problemelor de decizie decidabile în exponențială timp este definită ca:

EXPTEuME=⋃k∈NUDTEuME(2nuk){\ displaystyle {\ mathsf {EXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} \ left (2 ^ {n ^ {k}} \ right)}

Ierarhia timpului

În mod informal, teorema deterministică a ierarhiei timpului indică faptul că a avea mai mult timp permite să se decidă mai multe probleme. Mai precis, pentru toate funcțiile și astfel încât și este construibil în timp , se verifică următoarea includere strictă: f{\ displaystyle f}g{\ displaystyle g}fButuruga⁡f=o(g){\ displaystyle f \ log f = o (g)}g{\ displaystyle g}

DTEuME(f(nu))⊊DTEuME(g(nu)){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subsetneq {\ mathsf {DTIME}} (g (n))}

Legături cu alte clase

Clasele DTIME sunt legate de spațială complexitatea claselor dSpace și N-Space prin următoarele incluziuni, pentru orice edificabil funcție în spațiu: f{\ displaystyle f}

DTEuME(f(nu))⊆NUTEuME(f(nu))⊆DSPLAVSE(f(nu))⊆NUSPLAVSE(f(nu))⊆DTEuME(2O(f(nu))){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subseteq {\ mathsf {NTIME}} (f (n)) \ subseteq {\ mathsf {DSPACE}} (f (n)) \ subseteq {\ mathsf {NSPACE}} (f (n)) \ subseteq {\ mathsf {DTIME}} \ left (2 ^ {{\ mathcal {O}} (f (n))} \ right)}

Bibliografie

• (ro) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20 aprilie 2009, 579  p. ( ISBN  978-0-521-42426-4 , citit online ). 
• Sylvain Perifel, algoritmice complexitate , Editions elipse ,22 aprilie 2014, 432  p. ( ISBN  978-2-729-88692-9 , citit online ).