EXPTIME
De Wikipedia, la enciclopedia libre
En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n.
En términos de DTIME,
Se sabe que
y por el teorema de la jerarquía temporal:
- P ⊂ EXPTIME
de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas).
La clase de complejidad EXPTIME-completo es el conjunto de problemas de decisión que están en EXPTIME tales que todo problema de EXPTIME tiene una transformación polinomial hacia cada uno de los problemas de EXPTIME-completo. Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPTIME-completo puede ser visto como el conjunto de los problemas más difíciles de EXPTIME.
Como ejemplos de problemas EXPTIME-completos están el buscar a partir de una posición (en una versión generalizada) del Ajedrez, Damas, o Go y determinar si el primer jugador tiene una secuencia de jugadas ganadora a partir de allí. Estos juegos son EXPTIME-completos dado que las secuencias de jugadas a partir de una configuración dada es exponencial sobre el tamaño del tablero. (Cuando se tiene un juego generalizado en el cual el número de jugadas a partir de una configuración es polinómico en el tamaño del tablero, el mismo problema resulta generalmente PSPACE-completo.)
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
