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). 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 classes, sets of all of the decision problems which can be solved using a certain amount of computation time. If a problem of input size n can be solved in O ( f ( n ) ) {displaystyle O(f(n))} , we have a complexity class D T I M E ( f ( n ) ) {displaystyle mathrm {DTIME} (f(n))} (or T I M E ( f ( n ) ) {displaystyle mathrm {TIME} (f(n))} ). There is no restriction on the amount of memory space used, but there may be restrictions on some other complexity resources (like alternation). 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 asymptotically larger amounts of time always create strictly larger sets of problems. The well-known complexity class P comprises all of the problems which can be solved in a polynomial amount of DTIME. It can be defined formally as: P is the smallest robust class which includes linear-time problems D T I M E ( n ) {displaystyle mathrm {DTIME} left(n ight)} (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 Larger complexity classes can be defined similarly. Because of the time hierarchy theorem, these classes form a strict hierarchy; we know that P ⊊ E X P T I M E {displaystyle mathrm {P} subsetneq mathrm {EXPTIME} } , and on up. The exact machine model used to define DTIME can vary without affecting the power of the resource. Results in the literature often use multitape Turing machines, particularly when discussing very small time classes. In particular, a multitape deterministic Turing machine can never provide more than a quadratic time speedup over a singletape machine.