Probabilistic polynomial time hierarchy

Choose a rational $a^{\mathrm{\prime }}$ with $a<a^{\mathrm{\prime }}<b$, so $a^{\mathrm{\prime }}>1$. On input $x$ of length $n$, scan the input to determine $n$, parse its initial self-delimiting code $e$, and require $\mathrm{\mid }e\mathrm{\mid }\le c_0\log n$ for a fixed constant $c_0$; reject malformed or overlong descriptions. For a valid code, clock $M_e(x)$ at $T=\lceil n^{a^{\mathrm{\prime }}}\rceil$ transitions, treating timeout as rejection. Normalize ties by [F1] and swap accept/reject labels. The diagonal machine accepts with probability greater than $1\mathrm{/}2$ exactly when the normalized clocked machine for $e$ has probability below $1\mathrm{/}2$. The explicit code and bounded parser are supplied by [F4], with effectiveness and clock conventions in [F2,F3]. The time-$T$ source computation has probability denominator dividing $2^T$; the selector of [F1] uses this source clock, while the interpreter merely implements its exact probability.

By [F4], the clocked simulation of every active $O(\log n)$-bit description uses $O(T\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)$ time and preserves its fair-bit distribution. Reading the input length costs $O(n)$; code initialization costs $O(\log n)$; and the tie gadget costs $O(T)$. Since $a^{\mathrm{\prime }}>1$ and $a^{\mathrm{\prime }}<b$, their total is $O(n^{a^{\mathrm{\prime }}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}n)=o(n^b)$. Thus the diagonal language belongs to $\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(n^b)$ by its polynomial-clock specialization.

If some fixed $M_e$ decided the diagonal language in $O(n^a)$ time, take arbitrarily long strings beginning with its fixed code $e$. For all sufficiently large such lengths, $T=n^{a^{\mathrm{\prime }}}$ exceeds the running time of $M_e$, so the clocked computation in step 1.1 is exactly $M_e$'s computation. Tie normalization and label swapping then make the diagonal machine accept exactly on inputs where $M_e$ rejects, contradicting that $M_e$ decides the same language. Thus the diagonal language is not in $\mathrm{P}\mathrm{r}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(n^a)$. The reverse non-strict inclusion follows by running the faster machine unchanged under the larger time bound, so the containment is proper in the selected profile.