E (complexidade)
Na teoria da complexidade computacional, a Classe de complexidade E é o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo 2O(n) e, portanto, é igual à classe de complexidade DTIME(2O(n)).
E, ao contrário da classe semelhante EXPTIME, não é fechada sob redução em tempo polinomial.
Referências[editar | editar código-fonte]
- Allender, E.; Strauss, M. (1994), «Measure on small complexity classes with applications for BPP», Proceedings of IEEE FOCS'94, pp. 807–818, Predefinição:ECCC, DIMACS TR 94-18.
- Book, R. (1972), «On languages accepted in polynomial time», SIAM Journal on Computing, 1 (4): 281–287, doi:10.1137/0201019.
- Book, R. (1974), «Comparing complexity classes», Journal of Computer and System Sciences, 3 (9): 213–229, doi:10.1016/s0022-0000(74)80008-5.
- Impagliazzo, R.; Tardos, G. (1989), «Decision versus search problems in super-polynomial time», Proceedings of IEEE FOCS 1989, pp. 222–227.
- Watanabe, O. (1987), «Comparison of polynomial time completeness notions», Theoretical Computer Science, 54: 249–265, doi:10.1016/0304-3975(87)90132-0.
Ligações externas[editar | editar código-fonte]
- Complexity Zoo: Class E
P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |