En la teoría de la complejidad computacional , la clase de complejidad E es el conjunto de problemas de decisión que pueden resolverse mediante 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 muchos-uno en tiempo polinomial .
Relación con otras clases
E está contenido por NE .
Referencias
- Allender, E.; Strauss, M. (1994), "Medición de clases de complejidad pequeña con aplicaciones para BPP", Actas de IEEE FOCS'94 , págs. 807–818, ECCC TR94-004, DIMACS TR 94-18.
- Libro, R. (1972), "Sobre 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 problemas de búsqueda en tiempo superpolinomial", Actas de IEEE FOCS 1989 , págs. 222–227.
- Watanabe, O. (1987), "Comparación de nociones de completitud temporal polinómica", Theoretical Computer Science , 54 (2–3): 249–265, doi : 10.1016/0304-3975(87)90132-0.
Enlaces externos
