DTIME 📖 Wikipedia

許多重要的複雜度類都使用DTIME來定義，這些類別包含需要花費特定時間才能解決的問題，來作為分類。任何適當複雜度函式（proper complexity function）都可以用來定義複雜度類，但是只有特定的類別較有被研究的價值。概括說來，我們希望複雜度類對計算方式的變化來講足夠穩定，另外對副函式的合成來講會是封閉（close）的。

DTIME滿足時間譜系理論，這代表在漸進分析內較大的時間，所產生的時間複雜度類嚴格大於（大於且不等於）其他時間複雜度類。

有名的複雜度類P代表所有可以在多項式內的DTIME解決的問題。我們可以正式定義為：

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

P是包含了線性問題${\displaystyle {\mbox{DTIME}}\left(n\right)}$ 的最小堅固（robust）複雜度類（AMS 2004, Lecture 2.2, pg. 20）。另外，P也是我們認為"可以實際運算"的最大複雜度類（其他的複雜度類時間成長太快，一般認為計算是不實際的）。

一個大上很多的，使用DTIME的複雜度類是EXPTIME，包含了代表所有可以在指數時間內以圖靈機解決的問題。正式定義為：

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

我們可以用類似方法定義更大的複雜度類。因為時間譜系理論，這些複雜度類會組成嚴格的譜系（不會有哪個在上方者與下方相等）；換句話說，我們已知${\displaystyle {\mbox{P}}\subsetneq {\mbox{EXPTIME}}}$ ，並且依此類推。

實際操作以定義DTIME的機器，可以在不影響DTIME定義的前提之下，換成其他的某些機器。最後作結論時，常常會使用多帶圖靈機，特別是在定義某些很小的複雜度類時。更準確的說，一個多帶圖靈機不可能提供超過一般圖靈機平方時間以上的計算能力（Papadimitriou 1994, Thrm. 2.1）。

對時間進行常數倍數的加速並不影響DTIME內複雜度類的能力；因為常數倍數的加速永遠可以用增加圖靈機內狀態的方式達成。在Papadimitriou（1994, Thrm. 2.2）內的陳述，對任何語言L，

令L ${\displaystyle \in }$  DTIME(f(n))。對任何${\displaystyle \epsilon }$  > 0, L ${\displaystyle \in }$  DTIME(f'(n))，則f'(n) = ${\displaystyle \epsilon }$  f(n) + n + 2.

使用一般圖靈機以外的機器，我們會得到許多DTIME之外的推廣與限制。舉例來說，如果我們使用非確定型圖靈機，我們會得到名為NTIME的計算資源。對於DTIME的能力與其他計算資源的關係，我們仍所知甚少。

• American Mathematical Society. Rudich, Steven and Avi Wigderson (ed.) , 编. Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. 2004. ISBN 0-8218-2872-X. 
• Papadimitriou, Christos H. Computational Complexity. Reading, Massachusetts: Addison-Wesley. 1994. ISBN 0-201-53082-1.