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 formula_1 en EXPTIME als formula_2. 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.
Q205084
complexiteitstheorie
Concept
None
complexiteitsklasse
UNK
Q3262192
beslissingsproblemen
Concept
Q908207
O
Concept
Q163310
deterministische turingmachine
Concept
Q846354
P
MISC
None
EXPTIME
UNK
Q1933581
NTIME
MISC
Q163310
niet-deterministische turingmachine
Concept
Q1155831
DTIME
MISC
Q1155831
DTIME
MISC
Q1155831
DTIME
MISC
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
part of