Have a Question or Comment on this Article?

Categories: Complexity classes

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:

$\mbox{P} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}(n^k)$

Categories: Complexity classes

Top Encyclopedia Articles

Encyclopedia Index

human sexuality

human growth hormone

human genome project

<a href="http://c.casalemedia.com/c?s=61745&f=3&id=0" target="_blank"><img src="http://as.casalemedia.com/s?s=61745&u=http%3A%2F%2Fbiologydaily.com&f=3&id=0&if=0" width="120" height="600" border="0" alt=""/></a>

07-14-2008 23:18:10
The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy