EXPTIME
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/28 14:12 UTC 版)
EXPTIME（EXPとも）は、計算量理論において、チューリング機械で O(2p(n)) の時間で解ける全ての決定問題の集合である。なお、p(n) は n の多項式関数である。
- ^ Christos Papadimitriou (1994年). Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1 Section 20.1, page 491.
- ^ Papadimitriou (1994), section 20.1, corollary 3, page 495.
- ^ Chris Umans. “CS 21: Lecture 13 notes”. 2008年5月4日閲覧。 Slide 24.
- ^ Aviezri Fraenkel and D. Lichtenstein (1981年). “Computing a perfect strategy for n×n chess requires time exponential in n”. J. Comb. Th. A (31): 199–214.
- ^ J. M. Robson (1984年). “N by N checkers is Exptime complete”. SIAM Journal on Computing, 13 (2): 252–267.
- ^ J. M. Robson (1983年). “The complexity of Go”. Information Processing; Proceedings of IFIP Congress. pp. 413–417
- ^ Papadimitriou (1994), section 20.1, page 492.
[続きの解説]
「EXPTIME」の続きの解説一覧
- 1 EXPTIMEとは
- 2 EXPTIMEの概要
- 3 EXPTIME-完全
- 4 参考文献
- E X P T I M Eのページへのリンク
