Rp corp zpp bpp and pp classes

At a finite cutoff K, $\min (T,K)={\sum }_{j<K}{\mathbf{1}}_{\{T>j\}}$ on the finite space of K bits, so its expectation is ${\sum }_{j<K}{q}_j$. The equality follows pointwise by counting the j before the truncated halt. Thus F2 makes the displayed survival sum an exact extension of finite expected runtime. On the K-bit space $\mathbb{P}(\min (T,K)\ge K)=q_{K-1}$ for K positive, hence F3 gives $q_K\le q_{K-1}\le \mathbb{E}T\mathrm{/}K$. This also follows by adding the first K decreasing survival terms. If the expectation is finite, choosing arbitrarily large K shows $q_K\to 0$. No nonhalting mass has been silently omitted from a sum over halting prefixes.

Given expected runtime at most p(n), truncate the machine after $2p(n)$ simulated transitions, preserving any halt reached on the last allowed transition, and return unknown otherwise. Step 1.1 bounds unknown probability $q_{2p(n)}\le 1\mathrm{/}2$. A deterministic counter and a direct simulation of this one fixed machine cost polynomial time even if a counter scan is used at every transition. A returned yes/no is an actual terminal answer, so it is never wrong. This proves the bounded-unknown formulation from the expected-time one.

Conversely let a bounded-unknown algorithm cost at most p(n) per attempt. Repeat after unknown, with disjoint fresh blocks, until yes/no. Include input restoration and block generation in a larger polynomial bound P(n). Independence of complete blocks gives probability of reaching attempt r at most $2^{-(r-1)}$, by multiplying the conditional failure probability at each restart. Grouping the first KP(n) survival terms by attempts gives expected runtime at most $P(n){\sum }_{r=0}^{K-1}{2}^{-r}\le 2P(n)$. The finite sum identity follows on multiplying by one half and subtracting: ${\sum }_{r<K}{2}^{-r}=2(1-2^{-K})$. Every shorter prefix sum has the same upper bound by monotonicity, so F2 gives total expectation at most $2P(n)$. Step 1.1 gives probability-one halting; no attempt can return a wrong answer.

If L is in both RP and coRP, run its two bounded machines with independent bit blocks. An RP acceptance certifies membership; a coRP rejection certifies nonmembership; if neither occurs, output unknown. On a member the coRP machine never rejects and the RP machine certifies yes with probability at least one half. On a nonmember the RP machine never accepts and the coRP machine certifies no with probability at least one half. Both certificates cannot occur on any input branch: a zero-probability bad terminal event in a finite uniform space is empty. Thus this procedure is never wrong and has unknown probability at most one half.

From a bounded-unknown zero-error procedure obtain an RP machine by interpreting unknown as no, and a coRP machine by interpreting unknown as yes. The successful correct answer has probability at least one half on the relevant input side; the opposite wrong certificate has probability zero. Together with step 3.1 and the equivalence established above, this proves $\mathrm{Z}\mathrm{P}\mathrm{P}=\mathrm{R}\mathrm{P}\cap \mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$. Empty languages, full languages and empty input cause no change: the polynomial guard is positive and the correct deterministic output is permitted. None of these transformations changes PP's strict threshold to a BPP gap.