PP=RP consequences

PP=RP,coPP=coRP,PP=coPP=coRP=RP=ZPP=BPPP/poly

If PP=RP then you have a collapse to the first level, namely PH=NP. Assume PP=RP, since PP is closed under complement we have RP=coRP=ZPP, thus PP=ZPP.

Let L be a language in PPZPP, then there exists a probabilistic polynomial time Turing machine with access to a ZPP oracle O, call it MO, such that:

xLPr[MO accepts x]>12, and

xLPr[MO accepts x]1212nc.

Where nc is the running time of MO (in the standard definition, the second inequality appears with 12, however it can be improved to <12 and thus to the above).

Suppose that the Turing machine which decides O has expected runtime nd. Now, let us look at the machine M, which replaces each oracle call of MO by a t steps simulation of the ZPP machine for O, and repeats this simulation k times. If we come upon an oracle call, for which this process did not result in an answer (none of the k t-steps simulations halted), then M rejects.

Let H denote the event that all of the simulations halted in the given time, then:

Pr[M accepts x]=Pr[M accepts x|H]Pr[H]+Pr[M accepts x|H]Pr[H]=Pr[M accepts x|H]Pr[H]=Pr[MO accepts x]Pr[H].

Thus, we have:

xLPr[M accepts x]>12Pr[H], and

xLPr[M accepts x](1212nc)Pr[H]1212nc.

By Markov’s inequality, a single simulation does not halt with probability ndt, so k t-steps simulations do not output an answer with probability (ndt)k. By the union bound we have Pr[H]1nc(ndt)k112nc, for t=2nd and k=2nc. In this case M acheives the following separation:

xLPr[M accepts x]>12(12nc), and

xLPr[M accepts x]122nc<12122nc

Which proves LPP, since we can replace the constant 12 with any function f(x)FP.