DTIME
多くの重要な複雑性クラスが DTIME を使って定義される。それらのクラスは決定性時間のある量を使って解ける問題を含むものである。任意の時間構成可能関数を使って複雑性クラスを定義できるが、研究に値するクラスは限られている。一般に、複雑性クラスは計算モデルを変更しても安定していることが望ましく、サブルーチンの合成について閉じているのが望ましい。
DTIME は時間階層定理に従う。すなわち、漸近的に多くの時間を指定すると、常により大きな問題の集合が生成される。
よく知られている複雑性クラス P は、多項式量の DTIME で解ける問題のクラスである。形式的には以下のように定義される。
P = ⋃ k ∈ N DTIME ( n k ) {\displaystyle {\text{P}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}\left(n^{k}\right)}