|
DTIME（またはTIME）は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量（ステップ数）を表す。実際のリソース（プログラムの実行にかかる時間）と直接対応することから、最もよく研究されている計算資源の1つである。 DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 ''n'' の問題を解くのに ''f(n)'' の計算時間がかかる場合、その複雑性クラスは DTIME(f(n))（または TIME(f(n))）となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。 == DTIME による複雑性クラス == 多くの重要な複雑性クラスが DTIME を使って定義される。それらのクラスは決定性時間のある量を使って解ける問題を含むものである。任意の時間構成可能関数を使って複雑性クラスを定義できるが、研究に値するクラスは限られている。一般に、複雑性クラスは計算モデルを変更しても安定していることが望ましく、サブルーチンの合成について閉じているのが望ましい。 DTIME は時間階層定理に従う。すなわち、漸近的に多くの時間を指定すると、常により大きな問題の集合が生成される。 よく知られている複雑性クラス P は、多項式量の DTIME で解ける問題のクラスである。形式的には以下のように定義される。 : P は線形時間問題 DTIME(n) を含む最小の安定したクラスである (AMS 2004, Lecture 2.2, pg. 20)。また、Pは「現実的計算可能」な最大の複雑性クラスの一つと考えられている。 決定性時間を使うより大きなクラスとして EXPTIME がある。EXPTIME は決定性機械で指数関数時間を使って解ける問題のクラスである。形式的に示せば、以下のようになる。 : より大きな複雑性クラスも同様に定義できる。時間階層定理により、これらのクラスは厳密な階層を形成する。例えば P EXPTIME などとなる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「DTIME」の詳細全文を読む スポンサード リンク
|