Dタイム

計算複雑性理論において、DTIME（またはTIME）は、決定論的チューリングマシンの計算時間という計算リソースを表します。これは、「通常の」物理コンピュータが特定のアルゴリズムを用いて特定の計算問題を解決するのにかかる時間（または計算ステップ数）を表します。これは、重要な現実世界のリソース（コンピュータが問題を解決するのにかかる時間）と非常に密接に対応しているため、最もよく研​​究されている複雑性リソースの1つです。

リソースDTIMEは、複雑性クラス、つまり特定の計算時間で解決できるすべての決定問題の集合を定義するために使用されます。入力サイズnの問題インスタンスが⁠で解決できる場合${\displaystyle O(f(n))}$問題は複雑性クラスにある$\displaystyle {\mathsf {DTIME}}(f(n))}$（または）$\displaystyle {\mathsf {TIME}}(f(n))}$メモリ空間の使用量に制限はありませんが、他の複雑性リソース（交代など）には制限がある場合があります。

多くの重要な複雑性クラスは、 DTIME（決定論的な一定時間内に解決可能なすべての問題を含む）を用いて定義されます。適切な複雑性関数であればどれでも複雑性クラスを定義するために使用できますが、研究に役立つのは特定のクラスのみです。一般に、複雑性クラスは計算モデルの変更に対して堅牢であり、サブルーチンの合成に関して閉じていることが望ましいです。

DTIMEは時間階層定理を満たしており、漸近的に時間が長くなるにつれて、常に厳密に大きな問題群が生成されることを意味する。

よく知られている複雑性クラスPは、 DTIMEの多項式時間で解決できるすべての問題を含みます。形式的には次のように定義できます。

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

Pは、線形時間問題を含む最小のロバストクラスである。${\displaystyle {\mathsf {DTIME}}\left(n\right)}$（AMS 2004、講義2.2、20ページ）。P は、「計算上実行可能」と考えられる最大の複雑性クラスの1つです。

決定論的時間を使用するはるかに大きなクラスはEXPTIMEであり、これは指数時間で決定論的マシンを使用して解決可能なすべての問題を含みます。形式的には、次のようになります。

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}$

より大きな複雑性クラスも同様に定義できます。時間階層定理により、これらのクラスは厳密な階層を形成します。${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}$そして、さらに上へ。

P のような堅牢なクラスの場合、DTIME を定義するために使用される正確なマシン モデルは、リソースの能力に影響を与えることなく変更できます。計算複雑性に関する文献では、特に非常に小さな時間クラスを議論する場合、マルチテープ チューリング マシンに基づいて DTIME を定義することがよくあります。マルチテープ決定性チューリング マシンは、シングルテープ マシンに対して 2 乗以上の時間高速化を提供することは決してありません。^{[ 1 ]}

チューリングマシンの線形スピードアップ定理により、時間制限内の乗法定数は DTIME クラスの規模に影響を与えません。有限状態制御の状態数とテープアルファベットのサイズを増やすことで、常に一定の乗法的なスピードアップが得られます。Papadimitriou の記述では、言語Lに対して、 ^{[ 2 ]}は、

させて${\displaystyle L\in {\mathsf {DTIME}}(f(n))}$すると、任意の${\displaystyle \epsilon >0}$、${\displaystyle L\in {\mathsf {DTIME}}(f'(n))}$、 どこ${\displaystyle f'(n)=\epsilon f(n)+n+2}$。

決定性チューリングマシン以外のモデルを使用すると、DTIME にはさまざまな一般化と制限があります。たとえば、非決定性チューリングマシンを使用すると、リソースNTIMEが得られます。DTIME の表現力と他の計算リソースとの関係は、ほとんど理解されていません。数少ない既知の結果の 1 つは^{[ 3 ]}です。

${\displaystyle {\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))}$マルチテープマシン向け。これは拡張され、

${\displaystyle {\mathsf {DTIME}}(O(n{\sqrt {\log ^{*}n}}))\neq {\mathsf {NTIME}}(O(n{\sqrt {\log ^{*}n}}))}$サンタナム^{[ 4 ]}によると、${\displaystyle \log ^{*}n}$は反復対数です。

交代チューリングマシンを使用する場合、リソース ATIME があります。