Time hierarchy theorem: Difference between revisions

Revision as of 18:28, 3 August 2023

Revision as of 11:43, 5 August 2023

Line 33:

| doi = 10.1145/321356.321362| s2cid = 2347143

}}</ref> 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 [[constructible function|time-constructible function]]s ''f''(''n''),

:<math>\mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \mathsf{DTIME}(f(n){\log f(n)})</math>,

where [[DTIME]](''f''(''n'')) denotes the complexity class of [[decision problem]]s solvable in time [[big O notation|O]](''f''(''n'')). Note that the left-hand class involves [[little o]] notation, referring to the set of decision problems solvable in asymptotically '''less''' than ''f''(''n'') time.

The time hierarchy theorem for [[nondeterministic Turing machine]]s was originally proven by [[Stephen Cook]] in 1972.<ref>{{cite conference

Line 93:

===Statement===

<blockquote>'''Time Hierarchy Theorem.''' If ''f''(''n'') is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time ''o''(''f''(''n'')) but can be solved in worst-case deterministic time asymptotically bigger than ''O''(''f''(''n'')log ''f''(''n'')). For instance,Thus

:<math>\mathsf{DTIME}(o(f(n))) \subsetneq \mathsf{DTIME}\left (f(n)\log^2 f(n) \right).</math></blockquote>

'''Note 1.''' ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.<br>

For example,'''Example.''' thereThere are problems solvable in time ''n''log²''n'' but not time ''n''. This follows by setting <math>f(n) = n\log n</math>, since ''n'' is in

'''Note 2.''' The precise statement of the algorithm can be written using [[little o|little o notation]] as follows: if ''f''(''n'') is time-constructible, then

:<math>\mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)\subsetneq \mathsf{DTIME}\left (f(n) \right).</math>

For example, there are problems solvable in time ''n''log²''n'' but not time ''n'', since ''n'' is in

:<math>o\left(\frac{n\log^2 n}{\log {(n\log^2 n)}}\right).</math>

===Proof===