# Time hierarchy theorem for BPTIME

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?
• 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? Nov 30 '20 at 10:52
• As for (3), I suggest trying to see how a diagonalization would work in this case. Nov 30 '20 at 10:53
• (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? Nov 30 '20 at 11:02
• Given a Turing machine $T$, let $M(x)$ simulate $T$ for $|x|$ steps. If $T$ halts, toss a fair coin. Otherwise, output $1$. Nov 30 '20 at 11:07
• Nov 30 '20 at 14:52