NTIMEのソースを表示

'''NTIME(f(n))''' とは、[[計算複雑性理論]]における[[複雑性クラス]]の表現法であり、[[非決定性チューリング機械]]を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る[[決定問題]]の集合である。

よく知られている複雑性クラス '''[[NP]]''' は NTIME を使って次のように表現できる。

:<math>\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)</math>

同様に、'''[[NEXPTIME]]''' クラスも NTIME を使って定義される。非決定性[[時間階層定理]]によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。
{{Computer-stub}}

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]