「NTIME」の版間の差分
提供: miniwiki
ja>Minf 細 (テンプレートの追加) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:31時点における最新版
NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間(領域)を使って解くことが出来る決定問題の集合である。
よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。
- [math]\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)[/math]
同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性時間階層定理によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。