# Lack of time hierarchy theorem for probabilistic machines

A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has advice.

However, wouldn't the usual time-hierarchy theorem suffice in this case? For instance, we know that $BPP \subset EXP$, and since the ordinary time-hierarchy theorem implies that $EXP \subsetneq 2EXP$, we likewise know that $BPP \subsetneq 2EXP$. Could we not repeat with the bounded probabilistic version of $EXP$, and so on?

The deterministic time hierarchy theorem is based on our ability to simulate "weaker machines" (namely, those which run in time $T$ whereas the simulator is allowed to run in time $T\log T$), and know their response on a given input. This way, we can construct a machine running in time $T\log T$ which differs from every machine running in time $T$ on at least one input (simple diagonalization).
In the context of BPP however, the response on a given input (i.e. whether or not it belongs to the language accociated with the given probabilistic machine) is determined by the probability of accepting that input, namely if it exceeds some agreed upon threshold. You can of course compute this probability in a naive manner, and diagonlize just like in the deterministic case. This is similar to what you suggested, but calling this a time hierarchy theorem for probabilistic time is hardly fair, since the jumps are big enough to allow you to simply apply the deterministic time hierarchy theorem, avoiding any probabilistic issues. This does not answer for example whether or not $BPTime(n)\subsetneq BPTime(n^2)$.
• When you mean very loose, is the exact statement that we know that $BPTime(n)\subsetneq BPTime(2^{n})$ (because the simulator can compute whether the probabilities exceed an agreed upon threshold by iterating over all possible values of the random bits of the machine, but we do not know whether any simulator can do better)? Commented Nov 30, 2020 at 15:06