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,

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

Nós sabemos que:

P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE ${\displaystyle \subseteq }$ 2-EXPTIME ${\displaystyle \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 ${\displaystyle \subseteq }$ 2-EXPTIME, já que uma Máquina de Turing alternada é pelo menos tão poderosa quanto uma Máquina de Turing determinística.^[1]

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 ${\displaystyle 2^{2^{2^{n^{k}}}}}$. Isso pode ser generalizado para cada vez maiores limites de tempos.

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.^[2]