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 2 ^O(n) and is therefore equal to the complexity class DTIME(2^O(n)).

Contents

• Relationship to other classes
• References
• External links

E, unlike the similar class EXPTIME, is not closed under polynomial-time many-one reductions.

Relationship to other classes

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) This section does not cite any sources . Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed.(February 2023) ( Learn how and when to remove this message ) This section needs expansion. You can help by adding to it. (February 2023) ( Learn how and when to remove this message )

E is contained in NE.

References

• 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 .

External links

• Complexity Zoo : Class E