In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O(n) and is therefore equal to the complexity class DTIME(2O(n)).
E, unlike the similar class EXPTIME, is not closed under polynomial-time many-one reductions.
Relationship to other classes
editThis section has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
E is contained by NE.
References
edit- 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, 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 (2–3): 249–265, doi:10.1016/0304-3975(87)90132-0.