Hispanopedia Wiki
Articulo de referencia

EXPERIENCIA

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

Hispanopedia WikiContenido en espanolLectura gratuita

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 ser resueltos 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 dentro de 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 forma similar a EXPTIME, pero con un límite de tiempo doblemente exponencial . Esto puede generalizarse a límites de tiempo cada vez mayores.

EXPTIME también puede reformularse como la clase de espacio APSPACE, el conjunto de todos los problemas que pueden ser resueltos por una máquina de Turing alternada en el espacio polinomial.

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

Definición formal

En términos de DTIME ,

miincógnitaPAGTIMETROmi=⋃k∈norteDTIMETROmi(2nortek).{\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}

Relaciones con otras clases

Se sabe que

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

y también, por el teorema de la jerarquía temporal y el teorema de la jerarquía espacial , que

P ⊊ EXPTIME, NP ⊊ NEXPTIME y PSPACE ⊊ EXPSPACE

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 deben ser propias, pero se desconoce 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 de espacio APSPACE, el conjunto de todos los problemas que pueden ser resueltos por una máquina de Turing alternante en el espacio polinomial. Esta es una forma de ver que PSPACE ⊆ EXPTIME, ya que una máquina de Turing alternante es al menos tan potente como una máquina de Turing determinista. [ 3 ]

EXPTIME-completado

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 los problemas más difíciles en EXPTIME. Nótese 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 pueden resolverse en tiempo polinomial , según el teorema de jerarquía temporal .

En la teoría de la computabilidad , uno de los problemas indecidibles básicos es el problema de la parada : decidir si una máquina de Turing determinista (MTD) se detiene. Uno de los problemas EXPTIME-completos más fundamentales es una versión más simple de este, que pregunta si una MTD se detiene en una entrada dada en como máximo k pasos. Está en EXPTIME porque una simulación trivial requiere tiempo O( k ), y la entrada k se codifica 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 ko japonesas). [ 7 ] Estos juegos tienen la posibilidad de ser EXPTIME-completos porque pueden durar un número de movimientos exponencial en el tamaño del tablero. En el ejemplo del Go, se sabe que la regla ko japonesa implica EXPTIME-completitud, pero se desconoce si las reglas americanas o chinas del juego son EXPTIME-completas (podrían variar de PSPACE a EXPSPACE).

Por el contrario, los juegos generalizados que pueden durar un número de movimientos polinomial en función del 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.

Circuitos sucintos

Otro conjunto de problemas importantes que EXPTIME-completa tiene que ver con los circuitos concisos. La idea es que si podemos comprimir exponencialmente la descripción de un problema que requiere tiempo polinomial, entonces ese problema comprimido requeriría tiempo exponencial.

Como ejemplo, algunos gráficos pueden describirse sucintamente mediante un pequeño circuito booleano. El circuito tiene2norte{\displaystyle 2n}entradas, 1 salida ypagoly(norte){\displaystyle {\mathsf {poly}}(n)}puertas, por lo tanto, requierenpagoly(norte){\displaystyle {\mathsf {poly}}(n)}bits para describir. El circuito representa un gráfico con2norte{\displaystyle 2^{n}}vértices. Para cada par de vértices, si se introduce el código binario de los dos vértices en el circuito, la salida del circuito indica si los dos vértices están conectados por una arista.

Para muchos problemas de decisión P-completos que ocurren naturalmente sobre grafos, 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 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 grafos. [ 8 ]

Genéricamente, un circuito booleano connorte{\displaystyle n}entradas y una única salida es una representación sucinta de una cadena de2norte{\displaystyle 2^{n}}bits, que pueden usarse para describir algún otro objeto, como un grafo, una fórmula 3-CNF , etc. Para prácticamente todos los problemas NP-completos conocidos, la versión sucinta es NEXP-completa. En particular, SUCCINCT 3-SAT es NEXP-completa bajo reducciones en tiempo polinomial. [ 9 ] [ 10 ]

Referencias

  1. ↑ Papadimitriou, Christos (1994). Complejidad computacional . Addison-Wesley. ISBN 0-201-53082-1.Sección 20.1, página 491.
  2. ↑ Juris Hartmanis , Neil Immerman , Vivian Sewelson. "Conjuntos dispersos en NP − P: EXPTIME versus NEXPTIME". Information and Control , volumen 65, número 2/3, págs. 158–181. 1985. En la Biblioteca Digital de la ACM.
  3. ↑ Papadimitriou (1994 , pág. 495, Sección 20.1, Corolario 3) 
  4. ↑ Du, Ding-Zhu; Ko, Ker-I (2014), Theory of Computational Complexity , Wiley Series in Discrete Mathematics and Optimization (2.ª ed.), John Wiley & Sons, Proposición 3.30, ISBN  9781118594971.
  5. ↑ Fraenkel, Aviezri ; Lichtenstein, David (1981). "El cálculo de una estrategia perfecta para el ajedrez n × n requiere un tiempo exponencial en n". Journal of Combinatorial Theory . Serie A. 31 (2): 199–214 . doi : 10.1016/0097-3165(81)90016-9 .
  6. ↑ JM Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing . 13 (2): 252– 267. doi : 10.1137/0213018 .
  7. ↑ JM Robson (1983). "La complejidad del Go". Procesamiento de la información; Actas del Congreso IFIP . págs. 413–417 . 
  8. ↑ Papadimitriou (1994 , p. 495, sección 20.1) 
  9. ↑ Papadimitriou, Christos H.; Yannakakis, Mihalis (1986-12-01). "Una nota sobre representaciones sucintas de grafos" . Information and Control . 71 (3): 181– 185. doi : 10.1016/S0019-9958(86)80009-2 . ISSN 0019-9958 . 
  10. ↑ Williams, Ryan (14 de octubre de 2011). "Columna invitada: un recorrido informal por un límite de complejidad de circuitos" . ACM SIGACT News . 42 (3): 54–76 . doi : 10.1145/2034575.2034591 . ISSN 0163-5700 .