NTIME (Complexitat)

En teoria de la complexitat, la classe de complexitat NTIME(f(n)) és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista en un temps O(f(n)), on O és la notació de O gran, f és una funció qualsevol i n és la mida de l'entrada.^[1]^[2]

Això vol dir que pel problema donat, una màquina de Turing no determinista per una entrada de mida n funcionarà un temps O(f(n)) i sempre s'aturarà i acceptarà o rebutjarà l'entrada.^[3]

L'espai disponible per la màquina no està limitat, tot i que no pot sobrepassar O(f(n)), ja que el temps disponible limita l'espai que es pot utilitzar.

Relacions amb d'altres classes

La classe de complexitat NP es pot definir en termes de NTIME com segueix:

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

De manera similar, la classe NEXP es defineix en termes de NTIME:

${\displaystyle {\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

NTIME està relacionada amb DSPACE de la següent manera: per cada funció construïble f(n) es te

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$

Una generalització de NTIME és ATIME, definida amb màquina de Turing alternativa i resulta que

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$

Referències

[1]

[2]

[3]