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, unlike the similar class EXPTIME, is not closed under polynomial-time many-one reductions.

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 .
Book, R. (1974), "Comparing complexity classes", Journal of Computer and System Sciences 3 (9): 213–229 .
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 53: 249–265 .

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.