consequences
If then you have a collapse to the first level, namely . Assume , since is closed under complement we have , thus .
Let be a language in , then there exists a probabilistic polynomial time Turing machine with access to a oracle , call it , such that:
, and
.
Where is the running time of (in the standard definition, the second inequality appears with , however it can be improved to and thus to the above).
Suppose that the Turing machine which decides has expected runtime . Now, let us look at the machine , which replaces each oracle call of by a steps simulation of the machine for , and repeats this simulation times. If we come upon an oracle call, for which this process did not result in an answer (none of the -steps simulations halted), then rejects.
Let denote the event that all of the simulations halted in the given time, then:
.
Thus, we have:
, and
.
By Markov’s inequality, a single simulation does not halt with probability , so -steps simulations do not output an answer with probability . By the union bound we have , for and . In this case acheives the following separation:
, and
Which proves , since we can replace the constant with any function .