E(복잡성)
E (complexity)계산 복잡성 이론에서 복잡성 등급 E는 시간 2의O(n) 결정론적 튜링 기계에 의해 해결될 수 있는 의사결정 문제의 집합이므로 복잡성 등급 DTIME(2)과O(n) 동일하다.
E는 유사한 클래스 EXPTIME과 달리 다항 시간 다대일 축소에 따라 닫히지 않는다.
참조
- 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: 249–265, doi:10.1016/0304-3975(87)90132-0.
