1
$\begingroup$

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?
Improve this question
$\endgroup$
9
  • $\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$ – Yuval Filmus Nov 30 '20 at 10:52
  • $\begingroup$ As for (3), I suggest trying to see how a diagonalization would work in this case. $\endgroup$ – Yuval Filmus Nov 30 '20 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$ – BlackHat18 Nov 30 '20 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$ – Yuval Filmus Nov 30 '20 at 11:07
  • 2
    $\begingroup$ related cs.stackexchange.com/questions/92779/… $\endgroup$ – Ariel Nov 30 '20 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.