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