Incomputational complexity theory,DTIME (orTIME) is thecomputational resource ofcomputation time for adeterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certaincomputational problem using a certainalgorithm. 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).

The resourceDTIME is used to definecomplexity classes, sets of all of thedecision problems that can be solved using a certain amount of computation time. If problem instances of input sizen can be solved in⁠${\displaystyle O(f(n))}$⁠, the problem is in the complexity class⁠${\displaystyle \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(f(n))}$⁠ (or⁠${\displaystyle \mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(f(n))}$⁠). There is no restriction on the amount ofmemory space used, but there may be restrictions on some other complexity resources (likealternation).

Many important complexity classes are defined in terms ofDTIME, containing all of the problems that can be solved in a certain amount of deterministic time. Anyproper complexity function can be used to define a complexity class, but only certain classes are useful to study. In general, we desire our complexity classes to be robust against changes in the computational model, and to be closed under composition of subroutines.

DTIME satisfies thetime hierarchy theorem, meaning thatasymptotically larger amounts of time always create strictly larger sets of problems.

The well-known complexity classP comprises all of the problems that can be solved in a polynomial amount ofDTIME. It can be defined formally as:

${\displaystyle \mathsf{P}=\bigcup _{k\in \mathbb{N}}\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(n^k)}$

P is the smallest robust class that includes linear-time problems${\displaystyle \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(n\right)}$ (AMS 2004, Lecture 2.2, pg. 20).P is one of the largest complexity classes considered "computationally feasible".

A much larger class using deterministic time isEXPTIME, which contains all of the problems solvable using a deterministic machine inexponential time. Formally, we have

${\displaystyle \mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}=\bigcup _{k\in \mathbb{N}}\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(2^{n^k}\right).}$

Larger complexity classes can be defined similarly. Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that${\displaystyle \mathsf{P}⊊\mathsf{E}\mathsf{X}\mathsf{P}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}}$, and on up.

For robust classes, such as P, the exact machine model used to define DTIME can vary without affecting the power of the resource. The computational complexity literature often defines DTIME based onmultitape Turing machines, particularly when discussing very small time classes. A multitape deterministic Turing machine can never provide more than a quadratic time speedup over a singletape machine.^[1]

Due to thelinear speedup theorem for Turing machines, multiplicative constants in the time bound do not affect the extent of DTIME classes; a constant multiplicative speedup can always be obtained by increasing the number of states in the finite state control and the size of the tape alphabet. In the statement of Papadimitriou,^[2] for a languageL,

Let${\displaystyle L\in \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(f(n))}$. Then, for any${\displaystyle ϵ>0}$,${\displaystyle L\in \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(f^{\prime }(n))}$, where${\displaystyle f^{\prime }(n)=ϵf(n)+n+2}$.

Using a model other than a deterministic Turing machine, there are various generalizations and restrictions of DTIME. For example, if we use anondeterministic Turing machine, we have the resourceNTIME. The relationship between the expressive powers of DTIME and other computational resources are very poorly understood. One of the few known results^[3] is

${\displaystyle \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(O(n))\ne \mathsf{N}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(O(n))}$ for multitape machines. This was extended to

${\displaystyle \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(O(n\sqrt{{\log }^{\ast }n}))\ne \mathsf{N}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(O(n\sqrt{{\log }^{\ast }n}))}$ by Santhanam,^[4] where${\displaystyle {\log }^{\ast }n}$ is theiterated logarithm.

If we use analternating Turing machine, we have the resource ATIME.

• Computational resources
• Complexity classes

• Articles with short description
• Short description is different from Wikidata