E (complexity)
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.[1]
Relationship to other classes
[edit] | This section has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
![[icon]](/everything/wiki/File:Wiki_letter_w_cropped.svg){kind=small}
E is contained in NE, as E is the deterministic-time analogue of the nondeterministic class NE.[2]
References
[edit]- ↑ 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
- 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.