Time hierarchy theorem: Difference between revisions

Revision as of 04:34, 3 October 2005

Latest revision as of 19:58, 12 August 2025

(152 intermediate revisions by 81 users not shown)

Line 1:

{{short description|Given more time, a Turing machine can solve more problems}}

In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time. As a consequence, for every time-bounded [[complexity class]], there is a strictly larger time-bounded complexity class, and so the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones. The analogous theorems for space are the [[space hierarchy theorem]]s.

In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements about time-bounded computation on [[Turing machine]]s. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with ''n''² time but not ''n'' time, where ''n'' is the input length.

The time hierarchy theorem for [[Turing machine|deterministic multi-tape Turing machines]] was first proven by [[Richard E. Stearns]] and [[Juris Hartmanis]] in 1965.<ref>{{Cite journal

Both theorems use the notion of a [[constructible function|time-constructible function]]. A [[function (mathematics)|function]] ''f'' : '''N''' &rarr; '''N''' is time-constructible if there exists a deterministic [[Turing machine]] such that for every ''n'' in '''N''', if the machine is started with an input of ''n'' ones, it will halt after precisely ''f''(''n'') steps. All [[polynomial]]s with non-negative integral coefficients are time-constructible, as are exponential functions such as 2^''n''.

| last1 = Hartmanis | first1 = J. | author1-link = Juris Hartmanis

| last2 = Stearns | first2 = R. E. | author2-link = Richard E. Stearns

| doi = 10.2307/1994208

| journal = [[Transactions of the American Mathematical Society]]

| pages = 285–306

| title = On the computational complexity of algorithms

| volume = 117

| date = 1 May 1965

| issn = 0002-9947

| publisher = American Mathematical Society

| mr = 0170805

| jstor = 1994208| doi-access = free

}}

</ref> It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the [[Universal Turing machine#Efficiency|universal Turing machine]].<ref>{{cite journal

| last1 = Hennie

| first1 = F. C.

| last2 = Stearns

| first2 = R. E.

| author-link2 = Richard E. Stearns

|date=October 1966

| title = Two-Tape Simulation of Multitape Turing Machines

| journal = J. ACM

| volume = 13

| issue = 4

| pages = 533–546

| ___location = New York, NY, USA

| publisher = ACM

| issn = 0004-5411

| doi = 10.1145/321356.321362| s2cid = 2347143

| doi-access= free

}}</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(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'')). The left-hand class involves [[little o]] notation, referring to the set of decision problems solvable in asymptotically '''less''' than ''f''(''n'') time.

In particular, this shows that <math>\mathsf{DTIME}(n^a) \subsetneq \mathsf{DTIME}(n^b)</math> if and only if <math>a < b</math>, so we have an infinite time hierarchy.

== Deterministic time hierarchy theorem ==

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

| title = A hierarchy for nondeterministic time complexity

| first = Stephen A.

| last = Cook

| author-link = Stephen Cook

| year = 1972

| conference = STOC '72

| book-title = Proceedings of the fourth annual ACM symposium on Theory of computing

| publisher = ACM

| ___location = Denver, Colorado, United States

| pages = 187–192

| doi = 10.1145/800152.804913| doi-access= free

}}</ref> It was improved to its current form via a complex proof by Joel Seiferas, [[Michael J. Fischer|Michael Fischer]], and [[Albert R. Meyer|Albert Meyer]] in 1978.<ref>{{cite journal

| last1 = Seiferas

| first1 = Joel I.

| last2 = Fischer

| first2 = Michael J.

| author-link2 = Michael J. Fischer

| last3 = Meyer

| first3 = Albert R.

| author-link3 = Albert R. Meyer

|date=January 1978

| title = Separating Nondeterministic Time Complexity Classes

| journal = J. ACM

| volume = 25

| issue = 1

| pages = 146–167

| ___location = New York, NY, USA

| publisher = ACM

| issn = 0004-5411

| doi = 10.1145/322047.322061| s2cid = 13561149

| doi-access= free

}}</ref> Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today.<ref>{{cite journal

| first1 = Stanislav

| last1 = Žák

|date=October 1983

| title = A Turing machine time hierarchy

| journal = Theoretical Computer Science

| volume = 26

| issue = 3

| pages = 327–333

| publisher = Elsevier Science B.V.

| doi = 10.1016/0304-3975(83)90015-4| doi-access= free

}}</ref> The time hierarchy theorem for nondeterministic Turing machines states that if ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Little O notation|o]](''g''(''n'')), then

:<math>\mathsf{NTIME}(f(n)) \subsetneq \mathsf{NTIME}(g(n))</math>.

The analogous theorems for space are the [[space hierarchy theorem]]s. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of [[advice (complexity)|advice]].<ref>{{Cite book|doi=10.1109/FOCS.2004.33|title=45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|author=Fortnow, L.|pages=316|last2=Santhanam|first2=R.|chapter=Hierarchy Theorems for Probabilistic Polynomial Time|isbn=0-7695-2228-9|s2cid=5555450}}</ref>

==Background==

Both theorems use the notion of a [[constructible function|time-constructible function]]. A [[function (mathematics)|function]] <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> is time-constructible if there exists a deterministic [[Turing machine]] such that for every <math>n\in\mathbb{N}</math>, if the machine is started with an input of ''n'' ones, it will halt after precisely ''f''(''n'') steps. All [[polynomial]]s with non-negative integer coefficients are time-constructible, as are exponential functions such as 2^''n''.

==Proof overview==

We need to prove that some time class '''TIME'''(''g''(''n'')) is strictly larger than some time class '''TIME'''(''f''(''n'')). We do this by constructing a machine which cannot be in '''TIME'''(''f''(''n'')), by [[Cantor's diagonal argument|diagonalization]]. We then show that the machine is in '''TIME'''(''g''(''n'')), using a [[Simulation#Computer science|simulator machine]].

==Deterministic time hierarchy theorem==

===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 ''O''(''f''(''n'')log ''f''(''n'')). Thus

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

Equivalently, if <math>f, g</math> are time-constructable, and <math>f(n) \ln f(n) = o(g(n))</math>, then

<math display="block">\mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME} (g(n))</math></blockquote>

For any [[time constructible]] function <math>t: N \rightarrow N</math>, there exists

a language <math>A</math> that is decidable in time <math>O(t(n))</math> but not in time

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

<math>o(t(n)/\log t(n))</math>.

'''Example.''' <math>\mathsf{DTIME}(n) \subsetneq \mathsf{DTIME} (n (\ln n)^2) </math>.

===Proof===

We include here a proof of a weaker result, namely that '''DTIME'''(''f''(''n'')) is a strict subset of '''DTIME'''(''f''(2''n'' + 1)³), as it is simpler but illustrates the proof idea. See the bottom of this section for information on how to extend the proof to ''f''(''n'')log''f''(''n'').

To prove this, we first define the language of the encodings of machines and their inputs which cause them to halt within ''f''(|''x''|) steps:

We prove this by constructing a Turing machine <math>B</math> that is a <math>O(t(n))</math>

decider for a language <math>A</math> that is not decidable in <math>o(t(n)/\log

t(n))</math> time. In order to ensure that <math>B</math> finishes its computation in

time <math>O(t(n))</math> we include in <math>B</math> a counter of length <math>\log t(n)</math>,

which is the number of bits required to store the number <math>O(t(n))</math>.

: <math> H_f = \left\{ ([M], x)\ |\ M \ \text{accepts}\ x \ \text{in}\ f(|x|) \ \text{steps} \right\}. </math>

There are two parts to this construction. One part is to ensure that

<math>B</math> has a different output from all <math>o(t(n)/\log t(n))</math> Turing

machines. We do this by simulating a given Turing machine <math>M</math> on

input <math>\langle M\rangle 10^*</math>. If <math>M</math> finishes its computation

quickly enough (in time less than <math>t(n)/\log t(n)</math> where <math>n</math> is the

length of the input string), we construct <math>B</math> to have the opposite

output (this is similar to the digitalisation technique explained in the [[Diagonalization Lemma]]). But what if <math>M</math> does not halt in the alloted time? we still need

to make sure that <math>B</math> is a <math>O(t(n))</math> decider, so we add a counter to

<math>B</math> to make sure that it stops after <math>t(n)</math> steps.

Notice here that this is a time-class. It is the set of pairs of machines and inputs to those machines (''M'',''x'') so that the machine ''M'' accepts within ''f''(|''x''|) steps.

The basic structure of TM <math>B</math> is:

Here, ''M'' is a deterministic Turing machine, and ''x'' is its input (the initial contents of its tape). [''M''] denotes an input that encodes the Turing machine ''M''. Let ''m'' be the size of the tuple ([''M''], ''x'').

'''input''': string <math>w</math> with length <math>n</math>

'''if''' w 6 <math>w \not= \langle M\rangle 10^*</math> for some TM M '''then'''

reject

'''end if'''

calculate <math>\lceil t(n) / \log t(n)\rceil</math> and use this value to create counter <math>c</math>

'''while c > 0 do'''

simulate <math>M</math> with input <math>w</math> for 1 step

'''if''' <math>M</math> accepts '''then'''

reject

'''else if''' <math>M</math> rejects '''then'''

accept

'''end if'''

decrement <math>c</math>

'''end while'''

reject

We know that we can decide membership of ''H_f'' by way of a deterministic Turing machine ''R'', that simulates ''M'' for ''f''(''x'') steps by first calculating ''f''(|''x''|) and then writing out a row of 0s of that length, and then using this row of 0s as a "clock" or "counter" to simulate ''M'' for at most that many steps. At each step, the simulating machine needs to look through the definition of ''M'' to decide what the next action would be. It is safe to say that this takes at most ''f''(''m'')³ operations (since it is known that a simulation of a machine of time complexity ''T''(''n'') for can be achieved in time <math>O(T(n)\cdot|M|)</math> on a multitape machine, where |''M''| is the length of the encoding of ''M''), we have that:

Now we need to show that <math>B</math> halts within <math>O(t(n))</math> time. In order to

simulate <math>M</math>, <math>B</math> needs to keep track of <math>M</math>'s state, the tape symbol

<math>M</math> is currently reading, and <math>M</math>'s transition function. If <math>B</math> were

to store this information in one spot on its tape, as <math>B</math> simulates

<math>M</math> <math>B</math> may have to spend an arbitrary amount of time moving traveling

back and forth retrieving this information about <math>M</math>. So we introduce

a notion of tracks on <math>B</math>'s tape. In one track we will store

information about <math>M</math>, in the other track we will store information

about <math>B</math>'s current computation. We change <math>B</math>'s tape alphabet to a

set of pairs, one from each track. Then, in a constant amount of time

(dependent on the length of <math>M</math>, not the length of the entire input

string <math>w</math>) <math>B</math> can copy the information on the first track to the

current ___location on the second track. So, if <math>M</math> runs in time <math>g(n)</math>,

<math>B</math> can simulate it in time <math>O(g(n))</math>. We add the counter to a third

tape (also to cut down on unbounded time of traveling between the

current head position of <math>B</math> and the clock). The actual clock

updating operations require only <math>O(\log t(n))</math> because the length of

the clock is <math>\log (t(n) / \log t(n))</math>. So, if we allow <math>B</math> to

execute for <math>\lceil t(n) / \log t(n)\rceil</math> steps and each step

requires <math>O(\log t(n))</math> time, <math>B</math> will halt in time <math>O(t(n))</math>.

: <math> H_f \in \mathsf{TIME}\left(f(m)^3\right). </math>

Formally we need to show that <math>A</math> is not decidable in <math>o(t(n)/\log

t(n))</math> time. We prove this by contradiction. Assume that TM <math>M</math>

decides <math>A</math> in time <math>g(n)</math>, which is <math>o(t(n)/\log t(n))</math>. Then <math>B</math>

can simulate <math>M</math> in <math>d \cdot g(n)</math> time for some constant <math>d</math>. So,

for some constant <math>n_0</math>, <math>d \cdot g(n) < t(n) / \log t(n)</math> for all <math>n

\geq n_0</math>. Consider what happens when we run <math>B</math> on input <math>\langle

M\rangle 10^{n_0}</math>. This input is longer than <math>n_{0}</math>, which means

that <math>B</math> will have time to simulate <math>M</math> until it halts and then <math>B</math>

will do the opposite of <math>M</math> on the same input. Thus, <math>M</math> does not

decide <math>A</math> which contradicts our assumption. So, <math>A</math> is not decidable

in <math>o(t(n)/\log t(n))</math> time.

The rest of the proof will show that

== Non-deterministic time hierarchy theorem ==

: <math> H_f \notin \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) </math>

If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|o]](''g''(''n'')), then there exists a decision problem which cannot be solved in non-deterministic time ''f''(''n'') but can be solved in non-deterministic time ''g''(''n''). In other words, the complexity class [[NTIME]](''f''(''n'')) is a strict subset of NTIME(''g''(''n'')).

so that if we substitute 2''n'' + 1 for ''m'', we get the desired result. Let us assume that ''H_f'' is in this time complexity class, and we will reach a contradiction.

==Corollaries==

If ''H_f'' is in this time complexity class, then there exists a machine ''K'' which, given some machine description [''M''] and input ''x'', decides whether the tuple ([''M''], ''x'') is in ''H_f'' within

===Corrollary 1===

''For any two functions <math>t_1</math>, <math>t_2: \mathbb{N} \longrightarrow

\mathbb{N}</math>, where <math>t_1</math>(n) is o(<math>t_2</math>(n)/<math>log t_2</math>(n)) and <math>t_2</math> is

time constructible, TIME(<math>t_1</math>(n)) <math>\subset</math> TIME(<math>t_2</math>(n)).''

:<math>\mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>

This corollary shows that <math>t_1</math> and <math>t_2</math> belong to two different

classes of TIME hierarchies (and that TIME(<math>t_2</math>) includes

TIME(<math>t_1</math>). Note that we can say the two classes are different

because TIME(<math>t_1</math>) is a strict subset of TIME(<math>t_2</math>).

We use this ''K'' to construct another machine, ''N'', which takes a machine description [''M''] and runs ''K'' on the tuple ([''M''], [''M'']), ie. M is simulated on its own code by ''K'', and then ''N'' accepts if ''K'' rejects, and rejects if ''K'' accepts.

===Corrollary 2===

If ''n'' is the length of the input to ''N'', then ''m'' (the length of the input to ''K'') is twice ''n'' plus some delimiter symbol, so ''m'' = 2''n'' + 1. ''N'''s running time is thus

''For any two real number <math>1 \leq \epsilon_1 < \epsilon_2</math>,

TIME(<math>n^{\epsilon_1}</math>) <math>\subset</math> TIME(<math>n^{\epsilon_2}</math>)''

:<math> \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f\left( \left\lfloor \frac{2n+1}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f(n)\right). </math>

This corollary shows that polynomials of different degree are in

different TIME hierarchies and that the classes of the smaller degree

polynomials are strict subsets of the classes of the larger degree

polynomials.

Now if we feed [''N''] as input into ''N'<nowiki/>'' and ask the question whether ''N'' accepts its ''N''' description as input, we get:

===Corrollary 3===

* If ''N'' accepts' [''N'<nowiki/>'''''<nowiki/>''' ] (which we know it does in at most f(n) operations since K halts on ([''N'' ], [''N'<nowiki/>'''''<nowiki/>''']) in f(n) steps), this means that K rejects ([''N'<nowiki/>''], [''N'<nowiki/>'']), so ([''N''], [''N'<nowiki/>'']) is not in ''H_f'', and so by the definition of ''H_f'', this implies that ''N'' does not accept [''N'<nowiki/>''] in ''f''(''n'') steps. Contradiction.

''<math>P \subset EXPTIME</math>''

* If N rejects' [''N'<nowiki/>''] (which we know it does in at most f(n) operations), this means that K accepts ([''N'<nowiki/>''], [''N'<nowiki/>'''''<nowiki/>''']), so ([''N'' ], [''N'<nowiki/>'']) is in ''H_f'', and thus ''N'' does accept [''N'<nowiki/>''] in ''f''(''n'') steps. Contradiction.

By this corollary, the classes of polynomial time algorithms and

exponential time algorithms are different.

We thus conclude that the machine ''K'' does not exist, and so

: <math> H_f \notin \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>

===Extension===

The reader may have realised that the proof gives the weaker result because we have chosen a simple Turing machine simulation for which we know that

: <math> H_f \in \mathsf{TIME}(f(m)^3). </math>

It is known<ref>{{cite book |last1=Sipser |first1=Michael |title=Introduction to the Theory of Computation |date=27 June 2012 |publisher=CENGAGE learning |isbn=978-1-133-18779-0 |edition=3rd}}</ref> that a more efficient simulation exists which establishes that

: <math> H_f \in \mathsf{TIME}(f(m) \log f(m)) </math>.

==Non-deterministic time hierarchy theorem==

If ''g''(''n'') is a time-constructible function, and ''f''(''n''+1) = [[Big O notation|o]](''g''(''n'')), then there exists a decision problem which cannot be solved in non-deterministic time ''f''(''n'') but can be solved in non-deterministic time ''g''(''n''). In other words, the complexity class '''[[NTIME]]'''(''f''(''n'')) is a strict subset of '''NTIME'''(''g''(''n'')).

==Consequences==

The time hierarchy theorems guarantee that the deterministic and non-deterministic versionversions of the [[exponential hierarchy]] are genuine hierarchies: in other words '''[[P (complexity)|P]]''' &sub;⊊ '''[[EXPTIME]]''' &sub;⊊ '''[[2-EXP]]''' &sub;⊊ ..., and '''[[NP (complexity)|NP]]''' &sub;⊊ '''[[NEXPTIME]]''' &sub;⊊ '''2-NEXP''' &sub;⊊ ....

For example, <math>\mathsf{P} \subsetneq \mathsf{EXPTIME}</math> since <math>\mathsf{P} \subseteq \mathsf{DTIME} (2^n)\subsetneq \mathsf{DTIME} (2^{2n}) \subseteq \mathsf{EXPTIME}</math>. Indeed, <math>\mathsf{DTIME}\left(2^n\right) \subseteq \mathsf{DTIME}\left(o\left(\frac{2^{2n}}{2n}\right)\right) \subsetneq \mathsf{DTIME}(2^{2n})</math> from the time hierarchy theorem.

The theorem also guarantees that there are problems in '''P''' requiring arbitrarily large exponents to solve; in other words, '''P''' does not collapse to '''DTIME'''(''n''^''k'') for any fixed ''k''. For example, there are problems solvable in ''n''⁵⁰⁰⁰ time but not ''n''⁴⁹⁹⁹ time. This is one argument against [[Cobham's thesis]], the convention that '''P''' is a practical class of algorithms. If such a collapse did occur, we could deduce that '''P''' ≠ '''PSPACE''', since it is a well-known theorem that '''DTIME'''(''f''(''n'')) is strictly contained in '''DSPACE'''(''f''(''n'')).

However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of [[computational complexity theory]]: whether [[P = NP problem|'''P''' and '''NP''']], '''NP''' and '''[[PSPACE]]''', '''PSPACE''' and '''EXPTIME''', or '''EXPTIME''' and '''NEXPTIME''' are equal or not.

==Sharper hierarchy theorems==

The gap of approximately <math>\log f(n)</math> between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count. This can be done more efficiently on certain computational models. The sharpest results, presented below, have been proved for:

* The unit-cost [[random-access machine]]<ref>{{cite journal |last1=Sudborough |first1=Ivan H. |last2=Zalcberg |first2=A. |title=On Families of Languages Defined by Time-Bounded Random Access Machines |journal=SIAM Journal on Computing |date=1976 |volume=5 |issue=2 |pages=217–230 |doi=10.1137/0205018}}</ref>

* A [[programming language]] model whose programs operate on a binary tree that is always accessed via its root. This model, introduced by [[Neil D. Jones]]<ref>{{cite book |last1=Jones |first1=Neil D. |title=Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 |chapter=Constant time factors ''do'' matter |date=1993 |pages=602–611 |doi=10.1145/167088.167244|isbn=0-89791-591-7 |s2cid=7527905 }}</ref> is stronger than a deterministic Turing machine but weaker than a random-access machine.

For these models, the theorem has the following form:

<blockquote>If ''f''(''n'') is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case time ''af''(''n'') for some constant ''a'' (dependent on ''f'').</blockquote>

Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see [[Linear speedup theorem]]). Moreover, Ben-Amram proved<ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |title=Tighter constant-factor time hierarchies |journal=Information Processing Letters |date=2003 |volume=87 |issue=1 |pages=39–44|doi=10.1016/S0020-0190(03)00253-9 }}</ref> that, in the above models, for ''f'' of polynomial growth rate (but more than linear), it is the case that for all <math>\varepsilon > 0</math>, there exists a decision problem which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case time <math>(1+\varepsilon)f(n)</math>.

==See also==

* [[Space hierarchy theorem]]

==References==

{{Reflist}}

==Further reading==

The theorem also guarantees that there are problems in '''P''' requiring arbitrarily large exponents to solve; in other words, '''P''' does not collapse to DTIME(''n''^''k'') for any fixed ''k''. For example, there are problems solvable in O(''n''⁵⁰⁰⁰) time but not O(''n''⁴⁹⁹⁹) time. This is one argument against considering '''P''' to be a practical class of algorithms. This is unfortunate, since if such a collapse did occur, we could deduce that '''P''' &ne; '''PSPACE''', since it is a well-known theorem that '''DTIME'''(''f''(''n'')) is strictly contained in '''DSPACE'''(''f''(''n'')).

* {{Cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips | author-link = Michael Sipser }} Pages 310&ndash;313 of section 9.1: Hierarchy theorems.

* {{Cite book|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1| author-link = Christos Papadimitriou }} Section 7.2: The Hierarchy Theorem, pp.&nbsp;143&ndash;146.

{{Use dmy dates|date=September 2019}}

However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of [[complexity theory]]: whether [[Complexity classes P and NP|P and NP]], NP and [[PSPACE]], PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.

{{DEFAULTSORT:Time Hierarchy Theorem}}

[[Category:Computational complexity theory]][[Category:Theorems]]

[[Category:Structural complexity theory]]

[[Category:Theorems in computational complexity theory]]

[[Category:Articles containing proofs]]