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 pueden resolverse 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 polinómica 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 se puede reformular como la clase espacial APSPACE, el conjunto de todos los problemas que pueden resolverse mediante una máquina de Turing alterna 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 la jerarquía del tiempo y el teorema de la jerarquía del espacio , 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 la jerarquía temporal y el teorema de la 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 que al menos una de las tres primeras inclusiones y al menos una de las tres últimas inclusiones deben ser adecuadas, pero no se sabe cuáles lo son. También se sabe que si P = NP , entonces EXPTIME = NEXPTIME , la clase de problemas que se pueden resolver en tiempo exponencial mediante una máquina de Turing no determinista . [1] Más precisamente, E ≠ NE si y sólo si existen lenguas dispersas 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 alterna en el espacio polinomial. Esta es una forma de ver que PSPACE ⊆ EXPTIME, ya que una máquina de Turing alterna 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 uno en tiempo polinomial . En otras palabras, existe un algoritmo de tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas que están completos en EXPTIME podrían considerarse los problemas más difíciles en EXPTIME. Observe que aunque se desconoce si NP es igual a P, sí sabemos que los problemas EXPTIME-completos no están en P; Se ha demostrado que estos problemas no pueden resolverse en tiempo polinómico , mediante el teorema de la jerarquía temporal .
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 más fundamentales de EXPTIME-complete es una versión más simple de esto, que pregunta si un DTM se detiene en una entrada determinada en como máximo k pasos. Está en EXPTIME porque una simulación trivial requiere O( k ) tiempo, y la entrada k se codifica usando O(log k ) bits, lo que provoca 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 un número exponencial de pasos; No usará más. [4] El mismo problema con el número de pasos escritos 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 ko japonesas). [7] Estos juegos tienen la posibilidad de ser EXPTIME-completos porque los juegos pueden durar una cantidad 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 completo (podrían variar desde PSPACE hasta EXPSPACE).
Por el contrario, los juegos generalizados que pueden durar una cantidad de movimientos polinómicos en el tamaño del tablero suelen ser PSPACE-completos . Lo mismo ocurre con los juegos exponencialmente largos en los que la no repetición es automática.
Otro conjunto de problemas importantes de EXPTIME completo se relaciona con circuitos sucintos. Los circuitos sucintos son máquinas simples que se utilizan para describir algunos gráficos en un espacio exponencialmente menor. Aceptan dos números de vértice como entrada y salida si hay un borde entre ellos. Para muchos problemas de gráficos P-completos naturales , donde el gráfico se expresa en una representación natural como una matriz de adyacencia , resolver el mismo problema en una representación de circuito sucinta es EXPTIME-completo, porque la entrada es exponencialmente más pequeña; pero esto requiere una prueba no trivial, ya que los circuitos sucintos sólo pueden describir una subclase de gráficos. [8]
