En la teoría de la complejidad computacional , la clase de complejidad E es el conjunto de problemas de decisión que puede resolver una máquina de Turing determinista en el tiempo 2 O ( n ) y, por lo tanto, es igual a la clase de complejidad DTIME (2 O ( n ) ).
E , a diferencia de la clase similar EXPTIME , no está cerrada bajo reducciones de varios uno en tiempo polinómico .
Referencias
- Allender, E .; Strauss, M. (1994), "Medida en clases de pequeña complejidad con aplicaciones para BPP", Actas de IEEE FOCS'94 , págs. 807–818, ECCC TR94-004 , DIMACS TR 94-18.
- Libro, R. (1972), "Sobre los lenguajes aceptados en tiempo polinomial", SIAM Journal on Computing , 1 (4): 281–287, doi : 10.1137 / 0201019.
- Libro, R. (1974), "Comparación de clases de complejidad", Journal of Computer and System Sciences , 3 (9): 213-229, doi : 10.1016 / s0022-0000 (74) 80008-5.
- Impagliazzo, R .; Tardos, G. (1989), "Problemas de decisión versus búsqueda en tiempo superpolinomial ", Actas de IEEE FOCS 1989 , págs. 222-227.
- Watanabe, O. (1987), "Comparación de nociones de completitud de tiempo polinomial", Informática teórica , 54 : 249-265, doi : 10.1016 / 0304-3975 (87) 90132-0.