Time hierarchy theorem

Key takeaways

Time hierarchy theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Time hierarchy theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Time hierarchy theorem from memory before moving on to harder problems.

Reference excerpt

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. 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 n2 time but not n time, where n is the input length. The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the universal Turing machine. 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 time-constructible functions f(n),

D T I M E ( o ( f ( n ) ) ) ⊊ D T I M E ( f ( n ) log ⁡ f ( n ) ) , {\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)}),}

where DTIME(f(n)) denotes the complexity class of decision problems solvable in time 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 D T I M E ( n a ) ⊊ D T I M E ( n b ) {\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})} if and only if a < b {\displaystyle a<b} , so we have an infinite time hierarchy. The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then

N T I M E ( f ( n ) ) ⊊ N T I M E ( g ( n ) ) . {\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n)).}

The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice.

Background Both theorems use the notion of a time-constructible function. A function f : N → N {\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} } is time-constructible if there exists a deterministic Turing machine such that for every n ∈ N {\displaystyle n\in \mathbb {N} } , if the machine is started with an input of n ones, it will halt after precisely f(n) steps. All polynomials with non-negative integer coefficients are time-constructible, as are exponential functions such as 2n.

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 diagonalization. We then show that the machine is in TIME(g(n)), using a simulator machine.

Deterministic time hierarchy theorem

Statement 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

D T I M E ( o ( f ( n ) ) ) ⊊ D T I M E ( f ( n ) log ⁡ f ( n ) ) . {\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).}

Equivalently, if f , g {\displaystyle f,g} are time-constructable, and f ( n ) ln ⁡ f ( n ) = o ( g ( n ) ) {\displaystyle f(n)\ln f(n)=o(g(n))} , then

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Time hierarchy theorem

Start with the simplest possible case. Write down what Time hierarchy theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Time hierarchy theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Time hierarchy theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Time hierarchy theorem

In research: Time hierarchy theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Time hierarchy theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Time hierarchy theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Structural complexity theory, Theorems in computational complexity theory, so understanding it makes those chapters shorter.
In everyday life: Look for Time hierarchy theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Time hierarchy theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Time hierarchy theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Time hierarchy theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Time hierarchy theorem in simple terms?

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems.

Why does Time hierarchy theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Time hierarchy theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Time hierarchy theorem.