EXPTIME

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 tienen solución por 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 alternancias de cuantificadores o oráculos 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 se pueden resolver mediante una máquina de Turing alterna en espacio polinomial.

EXPTIME se relaciona con las otras clases básicas de complejidad de tiempo y espacio de la siguiente manera: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Además, por el teorema de la jerarquía temporal y el teorema de la jerarquía espacial, se sabe que P ⊊ EXPTIME, NP ⊊ NEXPTIME y PSPACE ⊊ EXPSPACE.

Definición formal

En términos de DTIME,

EXPTIME=⋃ ⋃ k▪ ▪ NDTIME()2nk).{displaystyle {mathsf {}=bigcup _{kin mathbb {N}{mathsf {DTIME}left(2^{n^{k}right). }

Relaciones con otras clases

Es sabido 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".

entonces, al menos una de las primeras tres inclusiones y al menos una de las últimas tres inclusiones deben ser correctas, pero no se sabe cuáles lo son. La mayoría de los expertos creen que todas las inclusiones son correctas. 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. Más precisamente, EXPTIME ≠ NEXPTIME si y solo si existen idiomas dispersos en NP que no están en P.

EXPTIME se puede reformular como la clase espacial APSPACE, el conjunto de todos los problemas que se pueden resolver mediante una máquina de Turing alterna en 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.

EXPTIME-completo

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, existe un algoritmo de tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas que son EXPTIME-completo pueden considerarse como los problemas más difíciles de EXPTIME. Note que aunque se desconoce si NP es igual a P, sabemos que los problemas de EXPTIME-completo 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 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 la mayoría de los k pasos. Está en EXPTIME porque una simulación trivial requiere un tiempo O(k), y la entrada k se codifica usando bits O(log k) 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 en un número exponencial de pasos; no usará más. El mismo problema con el número de pasos escritos en unario es P-completo.

Otros ejemplos de problemas completos EXPTIME incluyen el problema de evaluar una posición en ajedrez generalizado, damas o Go (con reglas japonesas de ko). 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, la regla japonesa ko es lo suficientemente intratable como para implicar EXPTIME-completo, pero no se sabe si las reglas estadounidenses o chinas más manejables para el juego son EXPTIME-completo.

Por el contrario, los juegos generalizados que pueden durar un número de movimientos que es polinomial 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-complete se relaciona con los 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 naturales P-completos, 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 breves solo pueden describir una subclase de gráficos.