DTIME
Nella teoria della complessità , DTIME (o TIME ) designa una famiglia di classi di complessità caratterizzate dalla loro complessità temporale su una macchina di Turing deterministica.
Più precisamente, è la classe dei problemi decisionali che, per un input di dimensione , possono essere risolti nel tempo da una macchina di Turing deterministica.
DTioME(f(non)){\ displaystyle {\ mathsf {DTIME}} (f (n))}non{\ displaystyle n}O(f(non)){\ displaystyle {\ mathcal {O}} (f (n))}
Definizioni
La classe P dei problemi decisionali decidibili da una macchina di Turing deterministica in tempo polinomiale rispetto alla dimensione dell'input può essere definita come:
P=⋃K∈NONDTioME(nonK){\ displaystyle {\ mathsf {P}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} (n ^ {k})}Allo stesso modo, la classe EXPTIME di problemi decisionali decidibili in tempo esponenziale è definita come:
EXPTioME=⋃K∈NONDTioME(2nonK){\ displaystyle {\ mathsf {EXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} \ left (2 ^ {n ^ {k}} \ right)}
Gerarchia temporale
Informalmente, il teorema deterministico della gerarchia temporale indica che avere più tempo consente di decidere più problemi. Più precisamente, per tutte le funzioni e tali che e sia costruibile nel tempo , si verifica il seguente rigoroso inserimento:
f{\ displaystyle f}g{\ displaystyle g}flogf=o(g){\ Displaystyle f \ log f = o (g)}g{\ displaystyle g}
DTioME(f(non))⊊DTioME(g(non)){\ displaystyle {\ mathsf {DTIME}} (f (n)) \ subsetneq {\ mathsf {DTIME}} (g (n))}
Collegamenti con altre classi
Le classi DTIME sono collegate alle classi di complessità spaziale DSPACE e NSPACE dalle seguenti inclusioni, per qualsiasi funzione costruibile nello spazio:
f{\ displaystyle f}
DTioME(f(non))⊆NONTioME(f(non))⊆DSPAVSE(f(non))⊆NONSPAVSE(f(non))⊆DTioME(2O(f(non))){\ 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)}Bibliografia
-
(en) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,20 aprile 2009, 579 p. ( ISBN 978-0-521-42426-4 , leggi in linea ).
-
Sylvain Perifel, Complessità algoritmica , Éditions Ellipses ,22 aprile 2014, 432 p. ( ISBN 978-2-729-88692-9 , leggi online ).