E (clase de complejidad)
En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)).
E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico.
Referencias
- Allender, E.; Strauss, M. (1994), «Measure on small complexity classes with applications for BPP», Proceedings of IEEE FOCS'94, pp. 807-818, ECCC TR94-004, DIMACS TR 94-18..
- Book, R. (1972), «On languages accepted in polynomial time», SIAM Journal on Computing 1 (4): 281-287..
- Book, R. (1974), «Comparing complexity classes», Journal of Computer and System Sciences 3 (9): 213-229..
- 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 53: 249-265..
Enlaces externos
- Allender, Eric; Loui, Michael C.; Regan, Kenneth W. «Complexity Classes».
| Control de autoridades |
|
|---|
Datos: Q1276623
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.