2-TIEMPO DE EXPERIENCIA

En la teoría de la complejidad computacional , la clase de complejidad 2-EXPTIME (a veces llamada 2-EXP ) es el conjunto de todos los problemas de decisión que se pueden resolver mediante una máquina de Turing determinista en un tiempo O (2 ^{2 p ( n )} ), donde p ( n ) es una función polinomial de n .

En términos de DTIME ,

${\displaystyle {\mathsf {2{\mbox{-}}TIEMPOEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {TIEMPODT}}\left(2^{2^{n^{k}}}\right).}$

Nosotros sabemos

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTAL .

2-EXPTIME también puede reformularse como la clase espacial AEXPSPACE, los problemas que pueden resolverse mediante una máquina de Turing alternada en el espacio exponencial. Esta es una forma de ver que EXPSPACE ⊆ 2-EXPTIME, ya que una máquina de Turing alternada es al menos tan poderosa como una máquina de Turing determinista. ^[1]

2-EXPTIME es una clase en una jerarquía de clases de complejidad con límites de tiempo cada vez más altos. La clase 3-EXPTIME se define de manera similar a 2-EXPTIME pero con un límite de tiempo triplemente exponencial . Esto se puede generalizar a límites de tiempo cada vez más altos.${\displaystyle 2^{2^{2^{n^{k}}}}}$

Algunos ejemplos de algoritmos que requieren al menos 2-EXPTIME incluyen:

• Cada procedimiento de decisión para la aritmética de Presburger requiere demostrablemente un tiempo al menos doblemente exponencial ^[2]
• Cálculo de una base de Gröbner sobre un cuerpo. En el peor de los casos, una base de Gröbner puede tener un número de elementos que es doblemente exponencial en el número de variables. Por otro lado, la complejidad en el peor de los casos de los algoritmos de base de Gröbner es doblemente exponencial en el número de variables así como en el tamaño de las entradas. ^[3]
• Encontrar un conjunto completo de unificadores asociativos-conmutativos ^[4]
• Satisfacer CTL ⁺ (que, de hecho, es 2-EXPTIME-completo) ^[5]
• La eliminación de cuantificadores en campos cerrados reales requiere un tiempo doblemente exponencial (ver Descomposición algebraica cilíndrica ).
• Calcular el complemento de una expresión regular ^[6]

Las generalizaciones de muchos juegos completamente observables son EXPTIME-completos. Estos juegos pueden considerarse como instancias particulares de una clase de sistemas de transición definidos en términos de un conjunto de variables de estado y acciones/eventos que cambian los valores de las variables de estado, junto con la cuestión de si existe una estrategia ganadora . Una generalización de esta clase de problemas completamente observables a problemas parcialmente observables eleva la complejidad de EXPTIME -completo a 2-EXPTIME-completo. ^[7]

• Función exponencial doble