https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=DTIME 2026-05-28T10:37:56Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=DTIME&diff=267917&oldid=prev 2020-06-08T17:55:36Z

<p></p> <p><b>Neue Seite</b></p><div>In der [[Komplexitätstheorie]] steht &#039;&#039;&#039;DTIME(f)&#039;&#039;&#039; oder auch kurz &#039;&#039;&#039;TIME(f)&#039;&#039;&#039; für die Menge der Zeit[[komplexitätsklasse]]n in Bezug auf eine deterministische [[Turingmaschine]]. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DTIME(f) ist die Klasse derjenigen [[Entscheidbar|Entscheidungsprobleme]], die auf einer deterministischen Turingmaschine in [[Landau-Notation|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.&amp;nbsp;a. das lineare [[Speedup-Theorem]].<br /> <br /> Man verwendet die Schreibweise &#039;&#039;DTIME(f)&#039;&#039; 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 (Komplexitätsklasse)|P]] wie folgt definiert: <br /> :&lt;math&gt;\mbox{P} = \bigcup_{k \ge 1} \mbox{DTIME}(n^k)&lt;/math&gt;.<br /> <br /> == Weblinks ==<br /> * {{Complexity Zoo|DTIME(f)|D#dtime}}<br /> <br /> {{DEFAULTSORT:Dtime}}<br /> [[Kategorie:Komplexitätsklasse]]</div>

imported>Megatherium