Dタイム

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

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

DTIMEの複雑度クラス

多くの重要な計算量クラスはDTIMEを用いて定義され、一定の決定論的時間で解けるすべての問題を含みます。計算量クラスを定義するには、任意の適切な計算量関数を使用できますが、研究に有用なのは特定のクラスだけです。一般的に、計算量クラスは計算モデルの変更に対して堅牢であり、サブルーチンの合成に対して閉じていることが求められます。

DTIME は時間階層定理を満たしており、漸近的に長い時間は常に厳密に大きな問題セットを生み出すことを意味します。

よく知られている複雑性クラスPは、多項式時間DTIMEで解けるすべての問題から構成されます。これは次のように正式に定義できます。

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

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

決定論的時間を用いるより大きなクラスは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クラスの規模に影響を与えない。有限状態制御における状態数とテープアルファベットのサイズを増やすことで、常に一定の乗法的な加速が得られる。パパディミトリウ^{[ 2 ]}の記述によれば、言語Lについて、

とします。すると、任意の に対して、となります。${\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の表現力と他の計算リソースとの関係は、ほとんど理解されていません。数少ない既知の結果の一つは^{[ 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 があります。

注記

1. パパディミトリウ 1994 年、Thrm. 2.1.
2. パパディミトリウ 1994 年、Thrm. 2.2.
3. ポールら 1983 .
4. サンタナム 2001 .

参考文献

• アメリカ数学会(2004).スティーブン・ルディッチ、アヴィ・ウィグダーソン（編）.計算複雑性理論. アメリカ数学会高等研究所. ISBN 0-8218-2872-X。

• パパディミトリウ, クリストス・H. (1994).計算複雑性. マサチューセッツ州レディング: アディソン・ウェスレー. ISBN 0-201-53082-1。

• Paul, Wolfgang J. ; Pippenger, Nick ; Szemerédi, Endre ; Trotter, William (1983).決定論と非決定論、および関連する問題について. 第24回計算機科学基礎シンポジウム. doi : 10.1109/SFCS.1983.39 .

• サンタナム、ラフル (2001).セパレータ、セグリゲータ、そして時間と空間について. 第16回IEEE計算複雑性会議. doi : 10.1109/CCC.2001.933895 . ISBN 0-7695-1053-1。