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é
![{\displaystyle {\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f97b41e77ae0afa5f441ed9c2cceabf0b19bdda6)
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 ![{\displaystyle (x,y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41cf50e4a314ca8e2c30964baa8d26e5be7a9386)
- Per tot x a L, existeix una cadena y de longitud
tal que ![{\displaystyle M(x,y)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a5764b190058d83d041ed464caadc438973f8b1)
- Per tot x no a L i totes les cadenes y de longitud
, ![{\displaystyle M(x,y)=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37817faffd503911c2282d917d0371d9f11bab1b)
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]
- ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.
- ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.
- ↑ 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.
|
---|
Considerades tractables | |
---|
Suposadament intractables | |
---|
Considerades intractables | |
---|
Jerarquia de classes | |
---|
Families de classes | |
---|