Time and Space Hierarchy Theorems: Examples and Counterexamples

For this fixed pair, decoding costs $O_M(n)$, clock construction costs $O_c(n+f(n))$, and simulation costs $O_M(n+cf(n)\log (cf(n)+2))$. Since $c$ is fixed and $f(n)\ge n$ eventually, their sum is $O_{M,c}(f(n)\log (f(n)+2))=o(g(n))$.

Therefore, for every fixed reserve $\epsilon >0$, there is $N_{M,c,\epsilon }$ such that all these padded codes of length $n\ge N_{M,c,\epsilon }$ fit within $\epsilon g(n)$ simulation time. Complementing the terminal answer adds constant time. Shorter codes can take the construction's timeout/default branch; no common padding threshold or simulation constant over all pairs is claimed.

Both sides of the displayed separation are deterministic classes.

The missing assertion would have to relate one of these classes to $NP$, whose definition allows existential certificates. No such relation appears in the hierarchy statement, so the P-versus-NP implication is absent.

Choose a valid coded machine $M$ that makes one transition and then halts, and give the fixed simulator $U_1$ the pair $⟨M,ϵ⟩$. The concrete code $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ has a unary arity header followed by all self-delimiting description fields, so its complete decoding requires reading more than one input cell.

By definition, $U_1$ completes that decoding before it simulates the one transition of $M$. Merely reaching and reading the later code cells takes more than one transition on the simulator's input tape. Thus this valid one-step computation costs more than one simulator step, contradicting the claimed universal bound at $n=1$.