NEXPTIME

En teoria de la complexitat, la classe de complexitat NEXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O (2^p(n)), on p(n) és una funció polinomial sobre n.^[1][2]

En termes de NTIME es té

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

També es pot definir NEXPTIME usant màquines de Turing deterministes com a verificadors. Un llenguatge L és a NEXPTIME si i només si existeixen els polinomis p i q i una màquina de Turing determinista M tal que:

• Per tot x i y, la màquina M s'executa en temps ${\displaystyle 2^{p(|x|)}}$per l'entrada ${\displaystyle (x,y)}$
• Per tot x a L, existeix una cadena y de longitud ${\displaystyle 2^{q(|x|)}}$tal que ${\displaystyle M(x,y)=1}$
• Per tot x no a L i totes les cadenes y de longitud ${\displaystyle 2^{q(|x|)}}$, ${\displaystyle M(x,y)=0}$

Sabem que

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

i també, pel teorema de la jerarquia del temps que

NP ⊊ NEXPTIME

Si P = NP, llavors NEXPTIME = EXPTIME, més precisament E ≠ NE si i només si existeixen llenguatges escassos a NP que no estan a P.^[3]

Referències