DTIME
|
|
In computational complexity theory, the complexity class DTIME(f(n)) or TIME(f(n)) is the set of decision problems that can be solved by a deterministic Turing machine using time O(f(n)), and unlimited space.
The well-known complexity class P can be defined in terms of DTIME as follows:
- <math>\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)<math>