In this paper, it is mentioned that BPTIME does not have a time hierarchy theorem, unlike DTIME. To quote the part where the author explains why:

It must hold that for any $x$, either $\Pr[M(x) = 1] \geq \frac{2}{3}$ or $\Pr[M(x) = 1] \leq \frac{1}{3}$. It is undecidable to test whether a machine $M$ satisfies this property and it is also unknown whether one can test if $M$ satisfies this property for a specific $x \in \{0, 1\}^{n}$ using less than $2^{n}$ steps.

Here are my questions:

  1. Why is it undecidable to test for any $x$ whether for a probabilistic Turing machine $M$, whether $\Pr[M(x) = 1] \geq \frac{2}{3}$ or $\Pr[M(x) = 1] \leq \frac{1}{3}$? Can we not directly infer it from the string corresponding to the description of $\langle M \rangle$?
  2. If (1) is "undecidable", why is the second fact (testing (1) for a specific $x \in \{0, 1\}^{n}$ using less than $2^{n}$ steps) merely "unknown"? Why doesn't the same proof of undecidability work?
  3. How are these two facts relevant to why BPTIME does not have a hierarchy theorem? In what specific step does the diagonalization argument break down when we are trying to prove a time hierarchy theorem for BPTIME?
  • $\begingroup$ The answer for (1) and (2) is quite simple - while you can check it for any single $x$ (by going over all possible values of the randomness, which takes exponential time), how would you test it for all $x$, of all lengths? $\endgroup$ Nov 30, 2020 at 10:52
  • $\begingroup$ As for (3), I suggest trying to see how a diagonalization would work in this case. $\endgroup$ Nov 30, 2020 at 10:53
  • $\begingroup$ (2) sounds clear. For a specific $x$, as you say, the best algorithm is exponential. It is unknown whether there is a better algorithm. But for (1), why is it "undecidable" and not merely "unknown"? Is there a formal proof of undecidability - perhaps a reduction to the halting problem? $\endgroup$
    – Sid Meier
    Nov 30, 2020 at 11:02
  • 1
    $\begingroup$ Given a Turing machine $T$, let $M(x)$ simulate $T$ for $|x|$ steps. If $T$ halts, toss a fair coin. Otherwise, output $1$. $\endgroup$ Nov 30, 2020 at 11:07
  • 2
    $\begingroup$ related cs.stackexchange.com/questions/92779/… $\endgroup$
    – Ariel
    Nov 30, 2020 at 14:52


Your Answer

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

Browse other questions tagged or ask your own question.