Turing Machine Time Complexity (DTIME) Measure
A Turing Machine Time Complexity (DTIME) Measure is a Computational Time Complexity Measure that represents the amount of time that takes a computing system to solve a computational task using a certain algorithm.
- AKA: Complexity Class DTIME, DTIME, Deterministic Turing Machine Computational Time Complexity, Turing Machine Running Time.
- Context:
- It can be calculated using a Run Time Complexity Evaluation Algorithm.
- Example(s):
- …
- Counter-Example(s):
- See: Computational Complexity Theory, Computational Resource, Deterministic Turing Machine, Computational Problem, Algorithm, Complexity Class, Decision Problem.
References
2020a
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/DTIME Retrieved:2020-4-5.
- 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 , we have a complexity class (or ). There is no restriction on the amount of memory space used, but there may be restrictions on some other complexity resources (like alternation).
- 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).
2020b
- (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Time_hierarchy_theorem Retrieved:2020-4-5.
- In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time.
The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine. Consequent to the theorem, for every deterministic time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions f(n), : [math]\displaystyle{ \mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \mathsf{DTIME}(f(n)) }[/math] . The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then : [math]\displaystyle{ \mathsf{NTIME}(f(n)) \subsetneq \mathsf{NTIME}(g(n)) }[/math] . The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice.
- In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time.
2015
- (Wikiversity, 2015) ⇒ https://en.wikiversity.org/wiki/Introduction_to_Complexity_Theory/Time_Complexity Last edited: 18 July 2015.
- QUOTE: The concept of complexity classes helps us group problems according to the way in which the are solved. Complexity classes have a complex and ill-understood relationship amongst each other.
One type of time complexity class is DTIME (sometimes refered to as TIME), a complexity class that describes the computational time of a problem on a deterministic Turing machine. All complexity classes that are based around the concept of time complexity on a deterministic Turing machine may be defined in terms of this class.
Another type of time complexity class is the non-deterministic analogue of DTIME, NTIME. The relationship between these two classes is not fully understood.
- QUOTE: The concept of complexity classes helps us group problems according to the way in which the are solved. Complexity classes have a complex and ill-understood relationship amongst each other.
2006
- (Sipser, 2006) ⇒ Michael Sipser (2006). "Introduction to the Theory of Computation (Second Edition)". In: Thomson - Course Technology. ISBN: 0-534-95097-3
- QUOTE: Let $M$ be a deterministic Turing machine that halts on all inputs. The running time or time complexity of $M$ is the function $f: \mathcal{N} \to\mathcal{N}$, where $f (n)$ is the maximum number of steps that $M$ uses on any input of length $n$. If $f (n)$ is the running time of $M$, we say that $M$ runs in time of (n)$ and that $M$ is an $f (n)$ time Turing machine. Customarily we use $n$ to represent the length of the input.