NEXPTIME

De Viquipèdia
Salta a la navegació Salta a la cerca

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ències[modifica]

  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.