DTIME

DTIME（TIME）: 計算時間の表現

DTIME、またはTIMEという概念は、計算複雑性理論の中で重要な役割を果たします。これは、決定性チューリング機械が特定の問題を解決する際に必要とされる計算時間を指しています。具体的には、ある問題に対して特定のアルゴリズムを用いる場合、その問題解決にかかるステップ数を示します。これにより、実際のコンピュータがプログラムを実行する際に必要とする時間をわかりやすく表現することが可能です。

このDTIMEは複雑性クラスを定義する際にも用いられます。複雑性クラスとは、特定の計算時間内で解ける全ての決定問題の集合を指し、これにより問題の難易度を評価することができます。例えば、入力の長さをnとした場合、入力問題を解くのに必要な計算時間がO(f(n))である場合、この問題はDTIME(f(n))に分類されます。この際、使用するメモリ空間には制限がありませんが、他の複雑性の尺度には制約が設けられることもあります。

DTIMEによる複雑性クラスの定義

DTIMEを用いて定義される複雑性クラスは重要なものが多く含まれています。これらのクラスは、決定性時間をベースに、様々な問題を解くための能力を示しています。任意の時間構成可能な関数を使って複雑性クラスを定義することもできますが、研究の対象となるクラスは限られているのが現状です。一般的に、複雑性クラスは計算モデルにかかわらず安定していることが望ましく、またサブルーチンの合成についても閉じていることが求められます。

DTIMEは時間階層定理という原則に従っています。この原則によると、漸近的に多くの時間を使うことで、より大きな問題の集合が常に生成されます。例えば、良く知られた複雑性クラスであるPは、多項式時間で解ける問題を含みます。形式的には、Pは次のように定義されます。

P = ⋃_{k ∈ N} DTIME(n^k)

このPは、線形時間で解ける問題を含む最小の安定したクラスであり、現実的な計算可能性を示す最大の複雑性クラスの一つとされています。また、決定性時間を用いるよりも大きなクラスとしてEXPTIMEがあります。EXPTIMEは、決定性チューリング機械が指数関数的な時間で解ける問題のクラスであり、具体的には以下のように表されます。

EXPTIME = ⋃_{k ∈ N} DTIME(2^{n^k})

このようにして、さらに大きな複雑性クラスも同様に定義することが可能であり、時間階層定理により、これらのクラスは明確に階層化されます。 したがって、例えばPはEXPTIMEの部分集合とされます。

計算機械モデルとDTIME

DTIMEの定義には様々な計算機械モデルが用いられますが、これらのモデルは資源に関する能力に対しては差がありません。特に、小規模な時間クラスの議論においては、多テープ型のチューリング機械がよく利用されます。多テープ型機械では、単一テープのチューリング機械に比べて最大でも2乗の時間的優位性しか得られないことが示されています。

DTIMEによるクラス表現には、時間の定数倍の違いは影響を与えないと言われています。このような性能向上は、有限状態制御における状態数の増加によって実現されることがあります。特に、Papadimitriou（1994）によれば、言語Lについて次のように表記されています。

L ∈ TIME(f(n)) であれば、あらゆるϵ > 0に対して、L ∈ TIME(f'(n))が成り立ちます。ただし、f'(n) = ϵf(n) + n + 2です。

DTIMEの拡張と制約

また、DTIMEは決定性チューリング機械以外のモデルを用いて一般化や制限を行うことも可能です。例えば、非決定性チューリング機械に基づくNTIMEという概念が存在し、これによって時間資源を表現することができます。DTIME及び他の計算資源の関係性は、未だに十分に解明されていない部分が多いのが実情です。さまざまな文献がこの領域の理解を深めようと取り組んでいます。

参考文献

• - American Mathematical Society. (2004). "Computational Complexity Theory".
• - Papadimitriou, C.H. (1994). "Computational Complexity". Addison-Wesley.

もう一度検索