E (复杂度)
在计算复杂度理论内,复杂度类E代表一个决定型问题的集合,里面的问题可以使用确定型图灵机在2O(n),等于复杂度类DTIME(2O(n))。
参考资料
- Allender, E.; Strauss, M., Measure on small complexity classes with applications for BPP, Proceedings of IEEE FOCS'94: 807–818, 1994, Template:ECCC, DIMACS TR 94-18.
- Book, R., On languages accepted in polynomial time, SIAM Journal on Computing, 1972, 1 (4): 281–287.
- Book, R., Comparing complexity classes, Journal of Computer and System Sciences, 1974, 3 (9): 213–229.
- Impagliazzo, R.; Tardos, G., Decision versus search problems in super-polynomial time, Proceedings of IEEE FOCS 1989: 222–227, 1989.
- Watanabe, O., Comparison of polynomial time completeness notions, Theoretical Computer Science, 1987, 53: 249–265.
外部链接
- Complexity Zoo: Class E