EXPTIME

En teoría de la complejidad computacional, la clase de complejidad EXPTIME, también denotada como EXP, incluye el conjunto de problemas de decisión que pueden resolverse mediante una máquina de Turing determinista en un tiempo acotado por una función exponencial. Específicamente, un problema pertenece a EXPTIME si existe un algoritmo que lo resuelve en tiempo O(2^p(n)), donde p(n) es una función polinomial del tamaño de la entrada n.

Esta clase contiene problemas que requieren una cantidad de tiempo exponencial en el peor caso, lo que los hace computacionalmente intratables para entradas grandes. EXPTIME incluye a clases como P y NP, aunque no se ha demostrado formalmente si estas inclusiones son estrictas. También se sabe que EXPTIME está contenida en EXPSPACE, y que contiene a PSPACE, es decir:

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE

Un ejemplo clásico de problema que pertenece a EXPTIME es el problema del juego generalizado del ajedrez, que se ha demostrado ser EXPTIME-completo bajo ciertas condiciones.

EXPTIME es fundamental para el estudio de los límites de lo computacionalmente factible, especialmente en el diseño y análisis de algoritmos para problemas complejos o con alta carga combinatoria.

En términos de DTIME,

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right).}$

Se sabe que

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE

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.)