Exptime

Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2^p(n)) tempo, onde p (n) é uma função polinomial de n.

Em termos de DTIME,

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

Sabemos que

P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE

e também, pelo time hierarchy theoremeo space hierarchy theorem, que

P $\subsetneq$ EXPTIME   and   NP $\subsetneq$ NEXPTIME   and   PSPACE $\subsetneq$ EXPSPACE

assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são. A maioria dos especialistas acreditam que todas as inclusões são próprias. É também conhecido que, se P = NP, então EXPTIME = NEXPTIME, a classe de problemas solucionáveis em tempo exponencial por uma máquina de Turing não-determinísticas. Mais precisamente, EXPTIME ≠ NEXPTIME se e somente se existem sparse languages no NP que não são em P.

EXPTIME também pode ser reformulado como o APSPACE classe de espaço, os problemas que podem ser resolvidos por uma alternating Turing machine no espaço polinomial. Esta é uma maneira de ver que EXPTIME PSPACE, já que uma máquina de Turing alternada é pelo menos tão poderoso quanto uma máquina de Turing determinista.

EXPTIME é uma classe em uma hierarquia de classes de complexidade exponencial, com limites de tempo cada vez mais elevados. A classe 2-EXPTIME é definida de forma semelhante ao EXPTIME mas com um tempo vinculado duplamente exponencial. Isto pode ser generalizado para limites de tempo cada vez mais altos.

EXPTIME-Completo

Um problema de decisão é EXPTIME-completo se ele estiver em EXPTIME, e cada problema na EXPTIME tem uma redução em tempo polinomial de muitos para ele. Em outras palavras, existe um algoritmo de tempo polinomial que transforma os casos de um, a instâncias do outro com a mesma resposta. Problemas que são EXPTIME-completo podem ser pensados como os problemas mais difíceis em EXPTIME. Observe que, embora não se saiba se NP é um subconjunto de P ou não, sabemos que os problemas EXPTIME-completo não estão em P. Tem sido provado que estes problemas não podem ser resolvidos em tempo polinomial, pelo teorema hierarquia de tempo.

Na teoria da computabilidade, um dos problemas básicos indecidíveis é o de decidir se uma máquina de Turing determinística (DTM) pára. Um dos mais fundamentais problemas EXPTIME-completo é uma versão mais simples deste, que pergunta se um pára DTM em no máximo k passos. É na EXPTIME porque uma simulação trivial requer tempo O (k), e os k entrada é codificado usando O (log k) bits. É EXPTIME-completo porque, grosso modo, podemos usá-lo para determinar se um máquina que resolve um problema EXPTIME aceita em um número exponencial de passos, não vai usar mais. O mesmo problema com o número de passos escritos em unário é P-completo.

Outros exemplos de problemas EXPTIME-completo incluem o problema da avaliação de uma posição no xadrez generalizada, ou damas. Estes jogos têm a chance de ser EXPTIME-Completo porque os jogos podem durar por uma série de movimentos que é exponencial no tamanho da placa.

Por outro lado, os jogos generalizados que podem durar por uma série de movimentos que é polinomial no tamanho da placa são muitas vezes PSPACE-completo. O mesmo vale para jogos exponencialmente longos em que a repetição não é automática.

Outro conjunto de importantes problemas EXPTIME-completo referem-se a circuitos sucintos. Circuitos sucintos são máquinas simples usado para descrever alguns gráficos no espaço exponencialmente menor. Eles aceitam dois números de vértices como entrada e saída será se existe uma aresta entre eles. Para muitos problemas de gráficos naturais P-completa, onde o gráfico é expresso em uma representação natural como uma matriz de adjacência, resolvendo o mesmo problema em uma representação com circuitos sucintos é EXPTIME-completo, porque a entrada é exponencialmente menor, mas isso exige a prova não trivial , uma vez que os circuitos sucintos só podem descrever uma subclasse de gráficos.

Bibliografia

• American Mathematical Society (2004). Rudich, Steven and Avi Wigderson (ed.), ed. Computational Complexity Theory. [S.l.]: American Mathematical Society and Institute for Advanced Study. ISBN 0-8218-2872-X 
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1