En la teoría de la complejidad computacional , la clase de complejidad EXPTIME (a veces llamada EXP o DEXPTIME ) es el conjunto de todos los problemas de decisión que se pueden resolver mediante una máquina de Turing determinista en tiempo exponencial , es decir, en tiempo O (2 p ( n ) ), donde p ( n ) es una función polinomial de n .
EXPTIME es una clase intuitiva en una jerarquía exponencial de clases de complejidad con oráculos o alternancias de cuantificadores cada vez más complejos. Por ejemplo, la clase 2-EXPTIME se define de manera similar a EXPTIME pero con un límite de tiempo doblemente exponencial . Esto se puede generalizar a límites de tiempo cada vez más altos.
EXPTIME también puede reformularse como la clase espacial APSPACE, el conjunto de todos los problemas que pueden resolverse mediante una máquina de Turing alternada en el espacio polinomial.
EXPTIME se relaciona con las otras clases básicas de complejidad temporal y espacial de la siguiente manera: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Además, por el teorema de jerarquía temporal y el teorema de jerarquía espacial , se sabe que P ⊊ EXPTIME, NP ⊊ NEXPTIME y PSPACE ⊊ EXPSPACE.
En términos de DTIME ,
Se sabe que
y también, por el teorema de jerarquía temporal y el teorema de jerarquía espacial , que
En las expresiones anteriores, el símbolo ⊆ significa "es un subconjunto de", y el símbolo ⊊ significa "es un subconjunto estricto de".
Por lo tanto, al menos una de las tres primeras inclusiones y al menos una de las tres últimas inclusiones deben ser propias, pero no se sabe cuáles lo son. También se sabe que si P = NP , entonces EXPTIME = NEXPTIME , la clase de problemas resolubles en tiempo exponencial por una máquina de Turing no determinista . [1] Más precisamente, E ≠ NE si y solo si existen lenguajes dispersos en NP que no están en P . [2]
EXPTIME puede reformularse como la clase espacial APSPACE, el conjunto de todos los problemas que pueden resolverse mediante una máquina de Turing alternada en el espacio polinomial. Esta es una forma de ver que PSPACE ⊆ EXPTIME, ya que una máquina de Turing alternada es al menos tan poderosa como una máquina de Turing determinista. [3]
Un problema de decisión es EXPTIME-completo si está en EXPTIME y cada problema en EXPTIME tiene una reducción de muchos a uno en tiempo polinomial. En otras palabras, hay un algoritmo en tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas que son EXPTIME-completos podrían considerarse como los problemas más difíciles en EXPTIME. Observe que, aunque se desconoce si NP es igual a P, sabemos que los problemas EXPTIME-completos no están en P; se ha demostrado que estos problemas no se pueden resolver en tiempo polinomial , por el teorema de la jerarquía del tiempo .
En la teoría de la computabilidad , uno de los problemas básicos indecidibles es el problema de la detención : decidir si una máquina de Turing determinista (DTM) se detiene. Uno de los problemas EXPTIME-completos más fundamentales es una versión más simple de este, que pregunta si una DTM se detiene en una entrada dada en como máximo k pasos. Está en EXPTIME porque una simulación trivial requiere O( k ) tiempo, y la entrada k está codificada usando O(log k ) bits, lo que causa un número exponencial de simulaciones. Es EXPTIME-completo porque, en términos generales, podemos usarlo para determinar si una máquina que resuelve un problema EXPTIME acepta en un número exponencial de pasos; no usará más. [4] El mismo problema con el número de pasos escrito en unario es P-completo .
Otros ejemplos de problemas EXPTIME-completos incluyen el problema de evaluar una posición en ajedrez generalizado , [5] damas , [6] o Go (con reglas japonesas ko). [7] Estos juegos tienen una probabilidad de ser EXPTIME-completos porque los juegos pueden durar un número de movimientos que es exponencial en el tamaño del tablero. En el ejemplo de Go, se sabe que la regla japonesa ko implica EXPTIME-completo, pero no se sabe si las reglas estadounidenses o chinas para el juego son EXPTIME-completas (podrían variar desde PSPACE hasta EXPSPACE).
Por el contrario, los juegos generalizados que pueden durar un número de movimientos polinómico en relación con el tamaño del tablero suelen ser PSPACE-completos . Lo mismo sucede con los juegos exponencialmente largos en los que la no repetición es automática.
Otro conjunto de problemas EXPTIME-completos importantes se relaciona con los circuitos sucintos. Los circuitos sucintos son máquinas simples que se utilizan para describir algunos grafos en un espacio exponencialmente menor. Aceptan dos números de vértice como entrada y salida si hay una arista entre ellos. Para muchos problemas de grafos P-completos naturales , donde el grafo se expresa en una representación natural como una matriz de adyacencia , resolver el mismo problema en una representación de circuito sucinto es EXPTIME-completo, porque la entrada es exponencialmente más pequeña; pero esto requiere una prueba no trivial, ya que los circuitos sucintos solo pueden describir una subclase de grafos. [8]
