NTIME
Nella teoria della complessità , NTIME designa una famiglia di classi di complessità caratterizzate dalla loro complessità temporale su una macchina di Turing non deterministica .
Più precisamente, è la classe dei problemi decisionali che, per un input di dimensione , possono essere risolti nel tempo da una macchina di Turing non deterministica.
NONTioME(f(non)){\ displaystyle {\ mathsf {NTIME}} (f (n))}non{\ displaystyle n}O(f(non)){\ displaystyle {\ mathcal {O}} (f (n))}
Definizioni
La classe NP dei problemi decisionali decidibili da una macchina di Turing non deterministica in tempo polinomiale rispetto alla dimensione dell'input può essere definita come:
NONP=⋃K∈NONNONTioME(nonK){\ displaystyle {\ mathsf {NP}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} (n ^ {k})}Allo stesso modo, la classe NEXPTIME di problemi decisionali decidibili da una macchina di Turing non deterministica in tempo esponenziale è definita come:
NONEXPTioME=⋃K∈NONNONTioME(2nonK){\ displaystyle {\ mathsf {NEXPTIME}} = \ bigcup \ limits _ {k \ in \ mathbb {N}} {\ mathsf {NTIME}} \ left (2 ^ {n ^ {k}} \ right)}
Gerarchia temporale
Informalmente, il teorema della gerarchia temporale non deterministica indica che avere più tempo consente di decidere più problemi. Più precisamente, per tutte le funzioni e tali che ed è in aumento e costruibile nel tempo , si verifica il seguente rigoroso inserimento:
f{\ displaystyle f}g{\ displaystyle g}f(non+1)=o(g(non)){\ Displaystyle f (n + 1) = o (g (n))}g{\ displaystyle g}
NONTioME(f(non))⊊NONTioME(g(non)){\ displaystyle {\ mathsf {NTIME}} (f (n)) \ subsetneq {\ mathsf {NTIME}} (g (n))}
Collegamenti con altre classi
Le classi NTIME sono collegate alle classi di complessità temporale deterministica DTIME e 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 ).