The complexity class DTIME

From Polymath1Wiki
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].