The complexity class DTIME

From Polymath Wiki
Revision as of 21:38, 28 July 2009 by WikiSysop (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

DTIME[math](f(n))[/math] is the class of decision problems that can be solved by a deterministic Turing machine in time [math]O(f(n))[/math].

Note that the time hierarchy theorem implies that relatively modest increases in [math]f(n)[/math] strictly increases the size of the complexity class DTIME[math](f(n))[/math]. More precisely, DTIME[math](f(n))[/math] is strictly contained in DTIME[math](f(n)\log f(n) \log \log f(n))[/math].