DTIME
Sign in to saveIn computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).
Article · Deutsch
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 bezeichnet. 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: .
Abstract from DBpedia / Wikipedia · CC BY-SA