Time and Space Hierarchy Theorems

Parse $z$ into three self-delimiting fields for a machine code, a canonical positive binary integer $c$, and an ignored padding string, rejecting trailing data. Use the finite-table multitape extension in An efficient universal simulation with a clock of the total decoder in A fixed effective binary encoding of deterministic one-tape Turing machines. Invalid fields return the fixed rejector pair with multiplier one. Every finite string is thereby decoded in finite time; listing all strings in length-lexicographic order gives the enumeration.

For each valid machine and multiplier, encoding these fields with successively longer padding supplies arbitrarily long codes for that pair. On input $x$, compute $b=ch(\mathrm{\mid }x\mathrm{\mid })$ using the fixed halting constructor. A step counter enforces $b$ simulated transitions, returning a halting result if it occurs within the budget and otherwise rejecting. This is the supplied step-clock interface.

For a cell cap, maintain the minimum and maximum visited position on each simulated tape, together with their total interval length. Each tape head moves to an adjacent cell, so these intervals count precisely its visited cells. Include the initial visited cells, rejecting immediately if they already exceed $b$, and reject before a transition that would enlarge the total beyond $b$. This effective monitor preserves every run staying within the cap; a loop inside it may continue forever. A separate configuration clock is needed to force such a run to halt.

If the relevant resource use of $M$ is $O(h(n))$, some fixed positive integer $c$ bounds it for all sufficiently large $n$. The enumeration includes this pair, and its corresponding monitor then preserves those computations. No claim about exceptional small lengths where $h(n)=0$, or about the monitor's own resource overhead, is implicit.

Define one fixed multitape procedure $R$ on $w$: decode $(M,c)$, reject malformed codes, construct $cf(n)$ for $n=\mathrm{\mid }w\mathrm{\mid }$, and run the clocked universal simulator on $M$ with simulated input equal to the entire word $w$. If the inner simulation returns, output the opposite of its result. This is a fixed interpreter; its decoding, clock construction, and universal-simulator transitions are all actual transitions of $R$.

The diagonal decider first computes $g(n)$ and constructs a unary timer of that length. The constructor costs $O(n+g(n))$. Converting its binary output to unary also costs $O(g(n)+\log (g(n)+2))$: repeatedly decrement a least-significant-bit-first counter and emit a mark, charging the traversed carry/borrow runs over the whole countdown. Their total is linear in the initial counter value. Rewind the timer, then execute $R$ with its fixed tapes and one additional timer tape. Each simulated transition of this fixed $R$ advances the timer once; at its end output a default rejection unless $R$ has already returned. The fixed transition table is incorporated directly, so this outer clock adds constant overhead per transition, not another universal-simulation factor.

On every input, including malformed descriptions and arbitrarily large encoded multipliers, the outer clock permits at most $g(n)$ transitions of $R$. All input-dependent decoding and inner-clock work are inside that clock. Thus total time is $O(n+g(n))=O(g(n))$, after treating finitely many lengths below the eventual floor separately.

Fix $(M,c)$. On its valid padded codes, decoding and copying the full simulated input cost $O_{M,c}(n)$; constructing the inner clock costs $O_c(n+f(n))$. By An efficient universal simulation with a clock, simulation costs $O_M(n+cf(n)\log (cf(n)+2))$. For this fixed pair the combined runtime of $R$ is $O_{M,c}(n+f(n)\log (f(n)+2))=o(g(n))$. It therefore finishes before the outer timer on every sufficiently long code of that pair. Arbitrarily long such codes exist by the enumeration, and the returned answer is the required complement.

The clocked diagonal construction decides a language $D$ in $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

If a machine running in $O(f)$ decided $D$, its code and a sufficiently long padded input would be a valid diagonal instance. The construction returns the opposite answer there, contradiction.

Every polynomial is $O(f)$, while $f\log f=o(g)$; both displayed bounds are time constructible.

The time hierarchy gives $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)⊊\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$. Since $P\subseteq \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$ and $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)\subseteq EXP$, this supplies a language in $EXP\setminus P$.

Construct a deterministic unary-input clock as follows: read its input, compute the binary value $g(n)$ with the fixed constructor, and perform $g(n)$ countdown iterations before halting. A least-significant-bit-first binary counter has linear total decrement cost (the numbers of bit changes form a geometric sum); returning its head after each decrement has the same bound. Thus the clock's actual running time $T(n)$ is $\mathrm{\Theta }(g(n))$ eventually, and can be arranged to be at least $n$ for every $n$. It is an exact running time in the terminology of Seiferas--Fischer--Meyer, even though $g$ was supplied only by an asymptotically bounded binary-output constructor.

Use the first corollary to Seiferas--Fischer--Meyer Theorem 4 (the identity-function case, p. 155): for an exact running time $T$, there is a binary language $D$ accepted within $T$ but outside every acceptance-time class with bound $a$ satisfying $a(n)\ge n$ and $a(n+1)=o(T(n))$. Here acceptance time means the length of a shortest accepting branch, and nonmembers have no accepting branch. This is the external separation result being invoked.

In particular, $D$ has an acceptor with an accepting branch of length at most $T(n)$ on each member. Run that fixed acceptor with the fixed unary clock from step 1.1 on separate tapes, interleaving one transition of each per round, and reject if the clock expires without acceptance. This preserves the language and forces every branch to halt within $O(T(n)+n)=O(g(n))$. The product machine has fixed finite control; this is direct clocking, not a claim of linear universal simulation. Hence $D\in \mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$ under the local all-branch convention.

If $D$ belonged to local $\mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$, a constant integer $C$ would bound its accepting times at every length by $a(n)=\max \{n,Cf(n),C\}$: enlarge $C$ to cover the finitely many exceptional lengths. Since $f(n)\ge n$ eventually, $a(n+1)=O(f(n+1))=o(g(n))=o(T(n))$. This contradicts the exclusion in step 2.1. Thus $D\mathrm{\notin }\mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$.

Nondecreasing $f$ gives $f(n)\le f(n+1)=o(g(n))$, so every all-branch $O(f)$ decider is an all-branch $O(g)$ decider. Together with steps 3.1 and 3.2 this proves the strict inclusion.

Retain the description and input, and store the active state, tape contents of visited cells, and head positions; update this finite configuration one transition at a time.

The description/input portion costs $O(n)$ cells and the current simulated configuration costs $O(s(n))$ cells. Updating one configuration at a time requires no history of the run and no halting clock. Hence the simulator uses $O(n+s(n))$ space, which is $O(s(n))$ under $n=O(s(n))$.

Compute $s(n)$ in binary, enforce that cap, and run the universal simulation with a binary counter through the at most $2^{cs(n)}$ configurations allowed by the cap. The simulation uses $O(s(n))$ space because $n=O(s(n))$.

A nonhalting deterministic run repeats a configuration before the counter expires, while a halting run is seen directly. Declare a fixed answer at expiry. The counter has $O(s(n))$ bits, so it and the simulator remain within $O(s(n))$ space.

Define a total diagonalizer $D$ on inputs of the self-delimiting form $x=⟨M,1^k⟩$. On such an input of length $n$, universally simulate $M(x)$ inside a fixed reserved fraction of the constructible $g(n)$-space budget, and reverse its answer; reject malformed inputs and use the forced-halting configuration cutoff if the simulation does not halt within that cap. The parser, retained input, simulated configuration, and cutoff counter together use $O(n+g(n))=O(g(n))$ space.

Suppose that a machine $M$ decides $D$ in at most $cf(n)$ space for all sufficiently large $n$. Since $n=O(f(n))$ and $f=o(g)$, sufficiently long paddings $x=⟨M,1^k⟩$ make the simulator's $O(n+cf(n))$ space fit strictly inside the reserved $g(n)$ cap. On any such $x$, the cutoff does not fire and $D(x)$ is the opposite of $M(x)$, a contradiction. Hence $D\mathrm{\notin }\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)$, while step 1.1 puts $D\in \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g)$. The reverse class inclusion is immediate from $f=o(g)$.

Read the machine and input as two delimited regions of the one read-only input $z$. Store their endpoints and the simulated input-head address in $O(\log (n+2))$ bits; the simulated input is endmarked and confined to its field. The effective finite-table coding underlying Effective enumeration of clocked machines applies also with one input tape designated read-only. Table fields and transition entries can be found by rescanning rather than copying the program.

For fixed $M$, store the work tapes as finite words with marked heads and interval endpoints. Its alphabet and tape count are constants, so a run using at most $b$ work cells has an encoding of length $O_M(b+1)$. Work-head addresses and the visited-cell counter add $O_M(\log (b+2))$ bits, and the finite-control encoding is constant. Before extending a visited interval, test the cell cap and reject on overflow, including an initial overflow. A binary cap itself uses $O(\log (b+2))$ bits. Thus the work bound is $O_M(b+\log (n+2))$.

Alternatively, count actual visited work cells in the simulator's binary representation, including configuration, cap, and scratch storage; enforce the encoded-storage limit before each visit to a new work cell. The input-field addresses and allocation counter need only $O(\log (n+2)+\log (b+2))$ auxiliary bits. Program lookup can compare indexed table fields by repeated scans in $O(\log (n+2))$ space. Reject malformed codes or an overflow. This gives the uniform bound, with faithful transition simulation whenever all required storage fits. Large alphabets or many tapes may trigger this guard even if the simulated cell count is at most $b$.

In either version, each completed simulated transition is exactly the transition selected by the encoded table, so induction gives faithfulness up to halting or overflow. No configuration-time counter was introduced, and thus within-cap loops are not falsely declared halting. The logarithmic floor absorbs the address term in each respective bound.

Compute the cap $s(n)$. The input is fixed and read-only, while finite control, work contents, and all head positions have only exponentially many configurations in $s(n)+\log n=O(s(n))$.

Use the universal simulator and a binary counter of $O(s(n))$ bits to count through that bound, stopping at expiry. A deterministic nonhalting computation repeats a configuration beforehand, so the forced answer makes the simulation total without exceeding $O(s(n))$ work space.

Apply Effective enumeration of clocked machines with the work-space bound $f$. On a code $z$ of length $n$ for $(M,c)$, first compare the required cap $cf(n)+O(\log n)$ with a fixed fraction of $g(n)$. If it does not fit, return a fixed answer; if it fits, simulate $M(z)$ with cap $cf(n)$, stop after its finite configuration bound, and return the opposite answer. Malformed codes also receive a fixed answer.

The preliminary comparison and the guarded simulation use $O(g(n))$ work cells on every input. For each fixed decoded pair, the simulator and its counter use $O(f(n)+\log n)$ cells; because $f=o(g)$ and the logarithmic floor is absorbed by $f$, every sufficiently long padded code for that pair passes the guard. Thus the diagonal language lies in $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g)$ without losing the eventual self-code needed below.

If the diagonal language were in $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)$, choose a clock multiplier $c$ for its decider and then a sufficiently long padded code $z$ for that pair. On input $z$ the diagonal machine simulates that same decider on $z$ and returns the opposite answer, a contradiction. Since $f=O(g)$ also gives the ordinary inclusion, the containment is strict.

Regard its endmarked input tape as an ordinary tape. By the local-model definition the input head is confined to its $n+2$ input positions, and the machine visits $O(s(n))$ work cells.

Therefore the total visited-cell count is $O(n+s(n))$, which is the claimed all-tapes DSPACE bound.

The local hierarchy applies to $f,g$, yielding a language in $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n)\setminus L$.

The bridge puts that language in $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(2n)$, hence in PSPACE. Since every $L$ computation is also polynomial all-tapes space, this proves the proper containment.

For the forward implication, validate $y$ and reject it if malformed. Otherwise recover $x$ and run the supplied $A$ decider. By the padding definition its answer is correct, and its cost is $O((N+1{)}^c+t(\mathrm{\mid }x\mathrm{\mid }))$. Since $p(n)>n$, the set of lengths $n$ with $p(n)=N$ is finite; maximizing gives the displayed worst-case bound, including lengths with no valid pad.

For the converse, on $x$ of length $n$ construct $x\mathrm{\#}{1}^{p(n)-n-1}$ and run the independently supplied padded-language decider. The exponent is nonnegative, including at $n=0$, and this valid pad belongs to the padded language exactly when $x\in A$. Construction costs $O(p(n{)}^c)$ and the decider costs $O(u(p(n)))$, giving the claimed sum.

The Gap Theorem for abstract measures (Hartmanis--Hopcroft, Theorem 7) applies to the given Blum measure and recursive $r>\mathrm{i}\mathrm{d}$. Its finite-stage construction uses only bounded tests of the decidable Blum predicate ${\mathrm{\Phi }}_i(x)=m$; it does not attempt to decide whether a program is eventually below a bound. The resulting recursive nondecreasing $t$ has the stage invariant that every indexed program eventually below $r\circ t$ is also eventually below $t$. Hence ${\mathcal{C}}_t={\mathcal{C}}_{r\circ t}$.

The Union Theorem for abstract measures (Hartmanis--Hopcroft, Theorem 16) applies to the effective strictly increasing sequence $(f_i)$. Its recursive finite-injury construction produces a recursive $t$ with two complementary invariants: every $f_i$ is eventually at most $t$, and each indexed program that is outside every ${\mathcal{C}}_{f_i}$ exceeds $t$ infinitely often. These give respectively ${\bigcup }_i{\mathcal{C}}_{f_i}\subseteq {\mathcal{C}}_t$ and the reverse inclusion.

Each hierarchy compares two deterministic classes or two nondeterministic classes at separated resource bounds, such as $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$ versus $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

By [L1] and the definition of $P$, the $P$ versus $NP$ question compares the unions of deterministic and nondeterministic polynomial-time classes. A separation needs one language in $NP$ outside every deterministic polynomial-time class; equality needs polynomial deterministic simulations for all $NP$ languages. The witnesses in step 1.1 only separate two bounds in the same model, and their bounds and witnesses may vary. These stated conclusions do not themselves provide either of the required cross-model arguments. This is a comparison of what the theorem statements assert, not a formal independence claim about their consequences in an axiomatic theory.

Fix a machine $M$ that halts after one transition without reading its input, and consider the valid pairs $⟨M,x⟩$ as $\mathrm{\mid }x\mathrm{\mid }$ grows. The simulated computation respects the bound $f=1$, but the specified universal simulator must first decode the complete self-delimiting pair and reject malformed encodings. This takes time at least linear in the unbounded pair length.

Hence this unrestricted diagonalizer is not an $O(1)$-time computation, despite every selected run of $M$ taking one step. A candidate's resource bound alone therefore does not bound decoding and universal-simulation overhead; a separate clock and a proved gap are needed.