Motivation
Giving a machine more time should let it solve more problems, but a proof must confront an obstacle: a simulator spends time interpreting the machine it simulates. If we diagonalize using exactly the time allowed to a purported faster machine, that simulation overhead can consume the entire budget. The deterministic time hierarchy theorem leaves a logarithmic gap large enough to absorb the overhead, then flips the simulated answer.
We will state the simulation fact used as background and prove the diagonal argument with explicit padding and quantifiers.
Definitions
For a function , is the class of languages decided by deterministic multitape Turing machines in time. A function is time-constructible here if a deterministic clock machine, given a unary input of length , runs for exactly steps before halting. We assume for all sufficiently large ; finitely many shorter lengths can be handled separately.
The standard universal-simulation fact we use is the following: there is a deterministic universal machine such that, for each fixed deterministic multitape machine , simulation of steps of on an input of length takes at most
steps of , including access to a finite code for . The constant depends on , not on or . The logarithm reflects efficient simulation of a fixed number of tapes; we use this standard result without proving the tape simulation here. A simulation must distinguish acceptance from rejection and continue until the simulated machine halts or the external clock expires.
A language belongs to if some machine decides it in time for a function with . This is a union over such bounds, not a single fixed constant-factor time class.
Theorem
Theorem 4.3.1
(A clocked time hierarchy)
For time-constructible satisfying the growth assumption above, there is a language in that is not in . Hence the latter class is a proper subclass of .
This statement is a conservative version with an explicit input-reading margin. It does not claim that every pair of bounds differing by only a constant factor yields a separation, nor does it remove the logarithmic simulation cost.
Corollary 4.3.2
(Strict separation of polynomial time budgets)
For fixed integers , the deterministic multitape classes satisfy . Standard polynomial clocks are understood up to harmless constant and lower-order clock conventions; those conventions give the same class. The result separates languages in these classes, rather than assigning an exact running time to a particular familiar problem.
Proof
Fix an effective enumeration of deterministic machines. Design the diagonal decider on a binary input of length as follows. If has the form , interpret its leading block as the index ; the suffix is padding and does not alter which machine is selected. Inputs with no zero may be assigned a fixed answer. Scan the input and write an actual unary string on a separate tape in time. Run the clock on that tape while simultaneously simulating on the whole input using . If the simulation halts before the clock, output the opposite answer. If the clock expires first, accept.
Put index decoding inside the clock
An effective enumeration need not produce its th machine description quickly as a function of . The uniform simulation process must therefore begin decoding or enumerating that description only after the clock starts. Charge every decoding, copying and simulation step to the clocked process. An input selecting an enormous or awkward description may time out before the machine is even initialized; the stipulated timeout answer still gives a perfectly valid decision.
For a fixed candidate index , decoding its finite description takes a fixed finite number of steps. The contradiction argument may absorb this into that candidate's simulation constant. Across all possible indices on arbitrary inputs, however, there is no need for a uniform bound on : the external clock bounds the actual work performed. Thus the proof does not accidentally multiply the global running-time bound of by an input-dependent, unbounded description constant.
The clock and interpreter are fixed multitape machines. A single combined machine can give each one step in turn using separate tape fields and a finite product of their control states. One such round costs only a fixed number of steps; long scans or code construction performed by the interpreter consume many rounds. Only the unary input tape and a few initial markers are prepared before timing begins, in time. In particular, we never write clock marks in advance or presume that a simulated tape-head move has zero implementation cost.
The simulation and clock take turns, so the actual time of is , including checking the input prefix, writing the unary tape and initializing the simulation. The initial unary tape has cells; no -sized object is created in advance. Since the clock halts, every branch of this deterministic computation halts. A machine that rejects within the allotted simulation is also flipped to acceptance; a timeout is not mistaken for a proof of nonmembership in the simulated language.
Use an asymptotic gap against one fixed candidate
Proof
(Contradiction with one fixed candidate)
Suppose for contradiction that a deterministic machine decides the language of in time . For this fixed , the universal-simulation bound is
Indeed by the growth assumption, and eventually , so . For every sufficiently large , choose any length- input beginning with ; padding makes such inputs available at arbitrarily large lengths. On that input the simulation finishes within the clock. The definition of then gives , contradicting the assumption that decides the same language.
The index-decoding cost is also for this fixed index, so it does not alter that conclusion. If the supposed decider has a running-time bound rather than exactly , its constant can likewise be absorbed: multiplication by a fixed constant preserves a little-o bound. Choose the eventual input-length threshold only after choosing this candidate and its constants. The proof needs no single threshold that works for every machine index at once.
Proof X-ray
Why the candidate is fixed before the threshold
The one non-routine move is the order of choices: the candidate is fixed first, and only then is the length threshold chosen. That order lets the machine-dependent constants and be absorbed, since holds for each fixed even though no single threshold works for every . Padding is the second ingredient: it makes the index a prefix of inputs at every large length, so an asymptotic bound can actually be used. The growth assumption pays for reading the input, and the little-o factor pays for the universal simulation. The argument closes by direct disagreement: on one padded input the simulation finishes inside the clock and outputs the opposite of . Without the gap the step fails. For the simulation cost is about for large , which exceeds the clock as soon as , so the clock may expire first and is not forced to disagree.
Notice that is never asked to compute , estimate a competing machine's asymptotic complexity or recognize which candidates satisfy the little-o condition. It follows the same finite clock rule on every input. The smaller-bound hypothesis appears only in the external contradiction, where it guarantees that a purported faster decider eventually finishes its simulation in time to be contradicted. Making the algorithm test that hypothesis would introduce an entirely different and unjustified computability requirement.
To see containment, every function is eventually , and finitely many small inputs can be absorbed into a constant. The diagonal language is in the larger class but outside the smaller one, so the containment is proper.
The growth condition is only eventual. Choose a fixed length beyond which it holds, and define the diagonal language arbitrarily on shorter inputs by a finite table. That table is part of a single finite machine description, even if its constant size is large. It does not give the machine answers for an unbounded family of lengths. The padded contradiction uses lengths beyond both this fixed cutoff and the selected candidate's convergence threshold, so the table cannot interfere.
Time constructibility is operational as well. Merely writing the binary numerical value of a proposed deadline does not provide the clock used in this proof. We assume an actual machine whose steps implement the deadline under the stated model. This assumption makes every timeout effective and every input decidable; it is not a condition that the diagonal machine subsequently has to recognize for arbitrary functions supplied as data.
Proof
(The ratio for polynomial clocks)
For the polynomial corollary, take a clock of order . The relevant ratio for a candidate order- bound is a constant multiple of , which tends to zero. For example, substituting reduces the convergence to . The hierarchy language is therefore outside every constant multiple of , while its construction stays within a constant multiple of . Ordinary containment also follows directly by allowing the smaller-budget decider extra unused time.
This is a strict separation of language classes, not a claim that all order- algorithms need that much time. Many languages in the larger class already have faster algorithms. Nor does the construction give a uniform procedure for finding tight lower bounds for arbitrary supplied programs: its single diagonal language is deliberately engineered to disagree with each sufficiently fast candidate on that candidate's padded inputs.
Counterexample mode
Half the time is not a smaller class
Claim: since for every , the theorem should give a language in that is not in . This is false. By definition allows steps, and , so the two classes are equal. The hypothesis of the theorem fails here: for and the ratio tends to infinity, not to zero. A separation needs a gap of at least a logarithmic factor in the proof above, not merely a smaller number.
Worked examples
Worked example 4.3.3
(Polynomial time bounds)
Take for , with a harmless time-constructible convention at small . The theorem provides a language decidable in time and not decidable in time: indeed . This separation concerns deterministic time classes under the chosen model. It does not identify a familiar natural problem with that exact complexity.
Worked example 4.3.4
(Why padding matters)
Suppose the target machine is , represented by prefix . There are strings with that prefix at every sufficiently large length, such as the prefix followed by as many zeroes as needed. The simulation constant may be enormous, but little-o convergence eventually beats any fixed . A single short code for would not let us invoke an asymptotic running-time bound at arbitrarily large input lengths.
Worked example 4.3.5
(One logarithm versus two logarithms)
Let at large lengths. A bound satisfies , so the theorem excludes a decider with that bound for the constructed language. In contrast gives ratio one and is not covered by this statement. Its simulation cost can remain a constant fraction of , with a candidate-dependent factor too large for this clock. Merely being numerically smaller than is therefore not the hypothesis proved here. Floor or ceiling conventions at sufficiently large lengths do not change either comparison.
Common mistakes
The diagonal machine must simulate the candidate on the same whole input on which their answers are compared. Also, saying “ is smaller than ” is not enough: the proof must pay for the universal simulator's factor and the input-handling cost. Finally, the theorem supplies a specially constructed language; it does not prove or give an unconditional lower bound for a named NP-complete problem.
Summary
A clocked simulation prevents diagonalization from running forever. Padding supplies arbitrarily long inputs naming each fixed candidate machine, and the little-o gap absorbs its fixed simulation constant. These ingredients create an unconditional strict hierarchy inside deterministic time, subject to the stated constructibility and simulation assumptions.
Exercises
Quick check
(Explain why .)
Solution · Answer
The ratio is , which tends to zero.
Quick check
(For , use the theorem to separate from .)
Solution · Answer
Since , the diagonal language belongs to and not to . Standard polynomial clocks meet the constructibility condition.
Quick check
(What does output when the simulated machine rejects before the clock? What if it has not halted at the deadline?)
Solution · Answer
It accepts in both cases: first by flipping rejection, second by the stipulated timeout rule. The two cases play different logical roles in the proof.
Quick check
(Why does the proof allow the universal-simulation constant to depend on ?)
Solution · Answer
Once a particular candidate machine is fixed, is independent of input length. Little-o convergence makes the overhead smaller than the clock for all sufficiently large padded inputs despite that fixed constant.
Quick check
(Does the theorem prove that SAT cannot be solved in quadratic time? Explain.)
Solution · Answer
No. The constructed separating language need not be SAT or even belong to NP. The theorem gives a separation of time classes, not a lower bound for every particular problem in the larger class.