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 el tiempo O (2 2 p ( n ) ), donde p ( n ) es un función polinomial de n .
En términos de DTIME ,
Sabemos
2-EXPTIME también se puede reformular como la clase espacial AEXPSPACE, los problemas que se pueden resolver mediante una máquina de Turing alternante en el espacio exponencial. Ésta es una forma de ver que EXPSPACE ⊆ 2-EXPTIME, ya que una máquina de Turing alternante 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.
2-EXPTIME-complete problemas
Las generalizaciones de muchos juegos completamente observables son EXPTIME-complete. Estos juegos pueden verse 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 -complete a 2-EXPTIME-complete. [2]
Ver también
Referencias
- ^ Christos Papadimitriou , Complejidad computacional (1994), ISBN 978-0-201-53082-7 . Sección 20.1, corolario 3, página 495.
- ^ Jussi Rintanen (2004). "Complejidad de la planificación con observabilidad parcial" (PDF) . Actas de la conferencia internacional sobre planificación y programación automatizadas . AAAI Press: 345–354.