E (complexity)

From Wikipedia, the free encyclopedia

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

E is less important to complexity theory than the similar class EXPTIME because it is not closed under polynomial-time many-one reductions.

[edit] References

• E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP, Proceedings of IEEE FOCS'94, pp. 807-818, 1994. ECCC TR94-004, DIMACS TR 94-18.
• R. Book. On languages accepted in polynomial time, SIAM Journal on Computing 1(4):281-287, 1972.
• R. Book. Comparing complexity classes, Journal of Computer and System Sciences 3(9):213-229, 1974.
• R. Impagliazzo and G. Tardos. Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, pp. 222-227, 1989.
• O. Watanabe. Comparison of polynomial time completeness notions, Theoretical Computer Science 53:249-265, 1987.

[edit] External links

• E at the Complexity Zoo