EXPTIME - 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 se pueden resolver mediante una máquina de Turing determinista en tiempo exponencial , es decir, en O (2 p ( n ) ) tiempo, 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 cada vez más complejos o alternancias de cuantificadores. 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 alternante en un 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 temporal y el teorema de la jerarquía espacial , se sabe que P ⊊ EXPTIME, NP ⊊ NEXPTIME y PSPACE ⊊ EXPSPACE.
Definicion formal
En términos de DTIME ,
Relaciones con otras clases
Se sabe que
y también, por el teorema de la jerarquía del tiempo y el teorema de la jerarquía del espacio , 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. La mayoría de los expertos creen que todas las inclusiones son adecuadas. 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 sólo si existen lenguas dispersas en NP que no están en P .
EXPTIME puede reformularse como la clase espacial APSPACE, el conjunto de todos los problemas que pueden resolverse mediante una máquina de Turing alternante en un espacio polinomial. Ésta es una forma de ver que PSPACE ⊆ EXPTIME, ya que una máquina de Turing alternante es al menos tan poderosa como una máquina de Turing determinista.
EXPTIME-complete
Un problema de decisión es EXPTIME-complete si está en EXPTIME y cada problema en EXPTIME tiene una reducción de varios uno en tiempo polinómico . En otras palabras, existe un algoritmo de tiempo polinomial que transforma las instancias de una en instancias de la otra con la misma respuesta. Los problemas que son EXPTIME-complete pueden considerarse los problemas más difíciles en EXPTIME. Observe que, aunque se desconoce si NP es igual a P, sabemos que los problemas EXPTIME-complete no están en P; Se ha comprobado que estos problemas no pueden resolverse en tiempo polinomial , 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 la mayoría de los k pasos. Está en EXPTIME porque una simulación trivial requiere tiempo O ( k ), y la entrada k se codifica utilizando bits O (log k ), lo que genera un número exponencial de simulaciones. Es EXPTIME-complete 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 EXPTIME-complete incluyen el problema de evaluar una posición en ajedrez generalizado , damas o Go (con reglas de ko japonesas). Estos juegos tienen la posibilidad de ser EXPTIME-complete 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 americanas o chinas más manejables para el juego son EXPTIME-complete.
Por el contrario, los juegos generalizados que pueden durar una cantidad de movimientos polinomiales en el tamaño del tablero suelen estar completos en PSPACE . 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 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 solo pueden describir una subclase de gráficos.