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 {\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 {\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 {\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 {\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}}$

Referències

1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529. 
3. «Complexity Zoo:N - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-07-21. [Consulta: 29 novembre 2018].