EXPTIME
En teoria de la complexitat, la classe de complexitat EXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps O(2p(n)), on p(n) és una funció polinomial sobre n.[1][2]
En termes de DTIME es té
Es coneix que
i pel teorema de la jerarquia temporal:
- P ⊂ EXPTIME
de manera que almenys una de les inclusions de la primera línia ha de ser estricta (es creu que totes ho son). També se sap que si P = NP, llavors EXPTIME = NEXPTIME, la classe de problemes resolubles amb temps exponencial per una màquina de Turing no determinista.[3] En concret, EXPTIME ≠ NEXPTIME si i només si existeixen llenguatges escassos a NP que no estan a P.[4]
La classe de complexitat EXPTIME-complet és la classe de problemes que estan a EXPTIME tals que tot problema d'EXPTIME té una transformació polinòmica cap a cada un dels problemes d'EXPTIME-complet. Dit d'una altra manera, existeix un algorisme que treballa en temps polinòmic que transforma les instàncies d'un problema en les instàncies de l'altra amb la mateixa resposta. El conjunt EXPTIME-complet pot esser vist com el conjunt de problemes més difícils d'EXPTIME.
Un exemple de problemes EXPTIME-complet son els de, a partir d'una posició dels escacs, dames o Go determinar si el primer jugador te una seqüència de jugades guanyadores. Aquests jocs son EXPTIME-complets, ja que la seqüència de jugades a partir d'una configuració donada és exponencial sobre la mida del tauler.
Referències modifica
- ↑ 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.
- ↑ H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821.
- ↑ 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.