1
$\begingroup$

The Wikipedia page on the time hierarchy theorem states:

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So if I understand correctly, there is an exponential time hierarchy for probabilistic machines, but it is not known if there is something finer exists? $\endgroup$
    – Mike Battaglia
    Jun 6, 2018 at 19:11
  • $\begingroup$ Yes. In addition to being very lose, this basically just follows from a simple application of the deterministic time hierarchy theorem, so it doesn't really deserve to be called a "hierarchy for probabilistic time" (this name is reserved for smarter arguments, hopefully referring to the probabilistic nature of things). $\endgroup$
    – Ariel
    Jun 6, 2018 at 19:17
  • $\begingroup$ 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)? $\endgroup$
    – Sid Meier
    Nov 30, 2020 at 15:06
  • $\begingroup$ That's the general idea (you might need another linear term for the naive simulation). $\endgroup$
    – Ariel
    Nov 30, 2020 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.