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 (2p(n)), on p(n) és una funció polinomial sobre n.
En termes de NTIME es té
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 per l'entrada Per tot x a L, existeix una cadena y de longitud tal que Per tot x no a L i totes les cadenes y de longitud ,
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.
Referències
Categoria:Complexitat computacional Categoria:Classes de complexitat