NTIME

計算複雑性理論において、計算複雑性クラス NTIME( f ( n ))は、時間O ( f ( n )) で実行される非決定性チューリングマシンによって解決できる決定問題の集合です。ここで、Oは大きな O 表記、fは何らかの関数、n は入力のサイズ (問題が決定される) です。

これは、サイズnの特定の入力に対して、時間O ( f ( n )) (つまり、 n が特定の値より大きい場合、 f ( n )の定数倍以内)で実行され、その入力に対する決定問題への回答が「いいえ」の場合は常に入力を「拒否」し、回答が「はい」の場合は、マシンは少なくとも 1 つの計算パスでその入力を「受け入れる」非決定性マシンが存在することを意味します。同様に、時間O ( f ( n )) で実行され、入力に対してO ( f ( n )) 長の証明書をチェックできる決定性チューリング マシンMが存在します。入力が「はい」インスタンスの場合は、少なくとも 1 つの証明書が受け入れられ、入力が「いいえ」インスタンスの場合は、証明書によってマシンが受け入れることはできません。

マシンが使用できるスペースには制限はありませんが、O ( f ( n ))を超えることはできません。これは、使用可能な時間によってテープが到達可能な量が制限されるためです。

よく知られている複雑性クラスNP は、NTIME に関して次のように定義できます。

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

同様に、クラスNEXPは NTIME に基づいて定義されます。

${\displaystyle {\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

非決定性時間階層定理によれば、非決定性マシンは漸近的に長い時間でより多くの問題を解決できます。

NTIMEはDSPACEと以下のように関連している。任意の時間構成関数t ( n )に対して、

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$。

NTIMEの一般化はATIMEであり、交代チューリングマシンで定義される。

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$。

複雑性動物園: NTIME(f(n))。