Exptime
De Wikipedia, a enciclopédia encyclopedia
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(2p(n)) tempo, onde p (n) é uma função polinomial de n.
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Dezembro de 2011) |
Em termos de DTIME,
Sabemos que
e também, pelo time hierarchy theoremeo space hierarchy theorem, que
- P EXPTIME and NP NEXPTIME and PSPACE 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.