Editing DTIME

In [[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).

The resource '''DTIME''' is used to define [[complexity class]]es, sets of all of the [[decision problem]]s which can be solved using a certain amount of computation time.  If a problem of input size ''n'' can be solved in {{tmath|O(f(n))}}, we have a complexity class {{tmath|\mathsf{DTIME}(f(n))}} (or {{tmath|\mathsf{TIME}(f(n))}}).  There is no restriction on the amount of [[Memory space (computational resource)|memory space]] used, but there may be restrictions on some other complexity resources (like [[Alternation (complexity)|alternation]]).

== Complexity classes in DTIME ==
Many important complexity classes are defined in terms of '''DTIME''', containing all of the problems that can be solved in a certain amount of deterministic time.  Any [[proper 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 the [[time hierarchy theorem]], meaning that [[asymptotic analysis|asymptotically]] larger amounts of time always create strictly larger sets of problems.

The well-known complexity class '''[[P (complexity)|P]]''' comprises all of the problems which can be solved in a polynomial amount of '''DTIME'''.  It can be defined formally as:

:<math>\mathsf{P} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(n^k)</math>

'''P''' is the smallest robust class which includes linear-time problems <math>\mathsf{DTIME}\left(n\right)</math> (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 is [[EXPTIME]], which contains all of the problems solvable using a deterministic machine in [[exponential time]].  Formally, we have
:<math> \mathsf{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{DTIME} \left( 2^{ n^k } \right) . </math>

Larger complexity classes can be defined similarly.  Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that <math>\mathsf{P} \subsetneq \mathsf{EXPTIME} </math>, and on up.

==Machine model==

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 on [[multitape Turing machine]]s, 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.<ref>Papadimitriou 1994, Thrm. 2.1</ref>

Due to the [[Linear 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,<ref>1994, Thrm. 2.2</ref> for a language {{mvar|L}},

:Let <math>L \in \mathsf{DTIME}(f(n))</math>. Then, for any <math>\epsilon > 0</math>, <math>L \in \mathsf{DTIME}(f'(n))</math>, where <math>f'(n) = \epsilon f(n) + n + 2</math>.

==Generalizations==

Using a model other than a deterministic Turing machine, there are various generalizations and restrictions of DTIME.  For example, if we use a [[nondeterministic Turing machine]], we have the resource [[NTIME]].  The relationship between the expressive powers of DTIME and other computational resources are very poorly understood. One of the few known results<ref>Paul Wolfgang, [[Nick Pippenger]], [[Endre Szemerédi]], William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. {{doi|10.1109/SFCS.1983.39}}</ref> is
:<math>\mathsf{DTIME}(O(n)) \neq \mathsf{NTIME}(O(n))</math>
for multitape machines. This was extended to
:<math>\mathsf{DTIME}(O(n\sqrt{\log^*n})) \neq \mathsf{NTIME}(O(n\sqrt{\log^*n}))</math>
by Santhanam.<ref>Rahul Santhanam, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392 On separators, segregators and time versus space], 16th Annual IEEE Conference on Computational Complexity, 2001.</ref>

If we use an [[alternation (complexity)|alternating Turing machine]], we have the resource ATIME.

==References==
{{Reflist}}
*{{cite book
 | author = American Mathematical Society
 | editor = [[Steven Rudich|Rudich, Steven]] and [[Avi Wigderson]]
 | title = Computational Complexity Theory
 | year = 2004
 | publisher = American Mathematical Society and [[Institute for Advanced Study]]
 | isbn = 0-8218-2872-X
| author-link = American Mathematical Society
 }}
*{{cite book
 | last = Papadimitriou
 | first = Christos H.
 | authorlink = Christos Papadimitriou
 | year = 1994
 | title = Computational Complexity
 | publisher = Addison-Wesley
 | location = Reading, Massachusetts 
 | isbn = 0-201-53082-1
}}

{{ComplexityClasses}}

{{DEFAULTSORT:Dtime}}
[[Category:Computational resources]]
[[Category:Complexity classes]]