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.[1][2]

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

PNPEXPTIME ⊆ NEXPTIME

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

NP ⊊ NEXPTIME

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

ReferènciesModifica

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. 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. Hartmanis, J.; Sewelson, V.; Immerman, N. «Sparse sets in NP-P: Exptime versus nexptime». Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 01-12-1983, pàg. 382–391. DOI: 10.1145/800061.808769.