NEXPTIME
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:46 UTC 版)
計算複雑性理論において、複雑性クラス NEXPTIME（NEXP）とは、非決定性チューリング機械で O(2p(n)) の時間（p(n) は任意の多項式）と無制限の領域を使って解ける決定問題の集合である。
| ||||||||||||
- ^ C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1 (section 20.1, pg.492)
- ^ 訳注: EXPTIMEにも同じ記述があるが、succinct circuit 自体はデータの表現方法であり、元の問題がP完全なら（succinct circuit を使えば）EXPTIME完全となり、NP完全ならNEXPTIME完全になるということであって、矛盾しているわけではない。
[続きの解説]
「NEXPTIME」の続きの解説一覧
- 1 NEXPTIMEとは
- 2 NEXPTIMEの概要
- 3 外部リンク
- NEXPTIMEのページへのリンク
