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:
- 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$?
- 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?
- 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?