DTIME

In der Komplexitätstheorie steht DTIME(f) oder auch kurz TIME(f) für die Menge der Zeitkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DTIME(f) ist die Klasse derjenigen Entscheidungsprobleme, die auf einer deterministischen Turingmaschine in O(f) Zeit lösbar sind. Man beachte, dass bei Angabe einer konkreten Funktion f die Bezeichnung DTIME(f) für eine einzelne Komplexitätsklasse steht, während bei Verwendung einer nicht näher definierten Funktion f die Bezeichnung DTIME(f) eine ganze Menge von Komplexitätsklassen meint. Darüber hinaus sieht man in der Regel von konstanten Faktoren bei der Funktionsdefinition von f ab und setzt somit DTIME(f) = DTIME(O(f)). Die Rechtfertigung für diese Vorgehensweise liefert u.a. das lineare Speedup-Theorem.

Man verwendet die Schreibweise DTIME(f) für alle Zeitklassen, die keinen eigenen Namen haben, so etwa im Rahmen der Zeithierarchiesätze. Darüber hinaus kann man sie zur Definition konkreterer Komplexitätsklassen einsetzen: So ist beispielsweise die wichtige Klasse P wie folgt definiert:

$\mbox{P} = \bigcup_{k \ge 1} \mbox{DTIME}(n^k)$.

Weblinks

• DTIME(f). In: Complexity Zoo. (englisch)