2-EXPTIME

Na teoria da Complexidade Computacional, a  classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(2^2p(n)), onde p(n) é uma função polinomial de n.

Em termos de DTIME,

$\text{2-EXPTIME}=\bigcup _{k\in \mathbb{N}}\text{ DTIME }\left(2^{2^{n^k}}\right).$

Nós sabemos que:

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE $\subseteq$ 2-EXPTIME $\subseteq$ ELEMENTARY.

2-EXPTIME também pode ser reformulado como a classe do espaço AEXPSPACE, os problemas que podem ser solucionados por uma Máquina de Turing Alternada em espaço exponencial. Esse é o único jeito para ver que EXPSPACE $\subseteq$ 2-EXPTIME, já que uma Máquina de Turing alternada é pelo menos tão poderosa quanto uma Máquina de Turing determinística.

2-EXPTIME é uma classe em uma hierarquia de classes de complexidade com crescente limite de tempo. a classe 3-EXPTIME é definida similarmente a 2-EXPTIME mas com limite de tempo exponencial triplo $2^{2^{2^{n^k}}}$. Isso pode ser generalizado para cada vez maiores limites de tempos.

Problemas 2-EXPTIME-completo

Várias generalizações de jogos totalmente observáveis são EXPTIME-completo. Esses jogos podem ser vistos como instâncias particulares de uma classe de sistemas de transição definida em termos de um conjunto de variaveis de estado e ações/eventos que mudam os valores das variáveis de estado, juntamente com a pergunta da existência de uma estratégia vencedora.

A generalização dessa classe de problemas totalmente observáveis a parcialmente observáveis leva a complexidade de EXPTIME-completo para 2-EXPTIME-completo.