E (complejidad)

En la teoría de la 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 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 es cerrada bajo reducciones muchos a uno en tiempo polinomial .

Relación con otras clases

E está contenido en NE .

Allender, E.; Strauss, M. (1994), "Medida en clases de complejidad pequeñas con aplicaciones para BPP", Actas de IEEE FOCS'94 , págs. 807–818 , ECCC TR94-004 , DIMACS TR 94-18 .
Book, R. (1972), "Sobre lenguajes aceptados en tiempo polinomial", SIAM Journal on Computing , 1 (4): 281– 287, doi : 10.1137/0201019.
Book, 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 en tiempo polinomial", Theoretical Computer Science , 54 ( 2–3 ): 249–265 , doi : 10.1016/0304-3975(87)90132-0.