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.

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.

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:

$𝖭𝖯=\bigcup _{k\in \mathbb{N}}𝖭𝖳𝖨𝖬𝖤(n^k)$

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

$𝖭𝖤𝖷𝖯=\bigcup _{k\in \mathbb{N}}𝖭𝖳𝖨𝖬𝖤(2^{n^k})$

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

$𝖭𝖳𝖨𝖬𝖤(t(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(t(n))$

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

$𝖭𝖳𝖨𝖬𝖤(t(n))\subseteq 𝖠𝖳𝖨𝖬𝖤(t(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(t(n))$