DTIME

In complexity theory , DTIME (f) or TIME (f) for short stands for the set of time complexity classes in relation to a deterministic Turing machine . If a concrete function f is given, this means: DTIME (f) is the class of those decision problems that can be solved on a deterministic Turing machine in O (f) time. Note that when specifying a specific function f, the designation DTIME (f) stands for a single complexity class, while when using an unspecified function f, the designation DTIME (f) designates a large number of complexity classes. In addition, one usually ignores constant factors in the function definition of f and thus sets DTIME (f) = DTIME (O (f)). The justification for this approach is u. a. the linear speedup theorem .

The notation DTIME (f) is used for all time classes that do not have their own name, for example in the context of the time hierarchy records. In addition, they can be used to define more specific complexity classes: For example, the important class P is defined as follows:

${\displaystyle {\mbox{P}}=\bigcup _{k\geq 1}{\mbox{DTIME}}(n^{k})}$.

Web links

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