DTIME
DTIME(またはTIME)は、計算複雑性理論における決定性チューリング機械での計算時間という計算資源を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要する時間の量(ステップ数)を表す。実際のリソース(プログラムの実行にかかる時間)と直接対応することから、最もよく研究されている計算資源の1つである。
DTIMEという資源は複雑性クラスの定義に使われる。複雑性クラスとは、ある特定の計算時間量で解ける全ての決定問題の集合である。入力長 n {\displaystyle n} の問題を解くのに O ( f ( n ) ) {\displaystyle O(f(n))} の計算時間がかかる場合、その複雑性クラスは DTIME ( f ( n ) ) {\displaystyle {\text{DTIME}}(f(n))} (または TIME ( f ( n ) ) {\displaystyle {\text{TIME}}(f(n))} )となる。このとき使用するメモリ空間量に制限はないが、他の複雑性尺度は制限されることもある。