DTIME

In de complexiteitstheorie is DTIME(f(n)), ook bekend als TIME(f(n)), een complexiteitsklasse die alle beslissingsproblemen bevat die in O(f(n)) tijd opgelost kunnen worden door een deterministische turingmachine.

Veel bekende complexiteitsklassen kunnen gedefinieerd worden in termen van DTIME. Zo kan P gedefinieerd worden als $\cup _{k=1}^{\infty }{\text{DTIME}}(n^{k})$ en EXPTIME als $\cup _{k=1}^{\infty }{\text{DTIME}}(2^{n^{k}})$. In verhouding tot NTIME geldt dat DTIME(f(n)) ⊆ NTIME(f(n)) voor elke functie f(n) aangezien de benodigde tijd op een niet-deterministische turingmachine die geen niet-determinisme gebruikt gelijk is aan een deterministische turingmachine.

Externe link

• (en) DTIME, Complexity Zoo