EXPTIME , 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(2^p(n)), donde p(n) es una función polinomial sobre n.

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

Un problema de decisión es EXPTIME-completo si es en EXPTIME, y todos los problemas de EXPTIME tienen tiempo-polinomial, o una reducción de la misma. En otras palabras, hay un algoritmo de tiempo polinómico que transforma los casos de uno a instancias del otro con la misma respuesta. Se podría pensar que los problemas que son EXPTIME-completo son los problemas más difíciles en EXPTIME. Nótese que aunque no sabemos si NP es un subconjunto de P o no, sí sabemos que los problemas EXPTIME-completo no están en P; se ha demostrado que estos problemas no pueden resolverse en tiempo polinomial.

En teoría de la computabilidad, uno de los problemas básicos no decidibles es el de decidir si una máquina de Turing determinista (DTM) se detiene(problema de la parada). Uno de los problemas más fundamentales EXPTIME-completo es una versión más sencilla de ello, que dice si un DTM detiene en a lo sumo k pasos. Es en EXPTIME porque obviamente una de simulación requiere O(k) tiempo, y la entrada k se codifica mediante O(log k) bits. Es EXPTIME-completo, ya que podemos usarlo para determinar si una máquina que resuelve un problema de EXPTIME acepta en forma exponencial el número de pasos; no va a usar más.

Otros ejemplos de problemas EXPTIME-completo incluyen el problema de evaluar una situación generalizada en el ajedrez, damas o Go (con las reglas japonesas ko). Estos juegos pueden ser EXPTIME-completo porque los juegos pueden durar de una serie de movimientos que es exponencial en el tamaño del tablero. En el ejemplo del Go, la regla japonesa del ko es lo suficientemente insoluble para implicar EXPTIME-completo, pero no se sabe si las más flexibles como las americanas o chinas son EXPTIME-completo.

Por el contrario, juegos generalizados que pueden durar una serie de movimientos que son polinómicos en el tamaño del tablero son a menudo PSPACE-completo.