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))。