I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer science professors about the problem and he proposed the following proof sketch:

Proof (sketch):

We know $A_{TM} \le_m A_{PTM}$.

Construct a decider $D$ that given a Probabilistic Turing Machine $M$ and a string $x$, $D$ accepts if $M$ accepts $x$, and rejects otherwise. As $A_{TM} \le_m A_{PTM}$, a solution to $A_{PTM}$ would yield a solution to $A_{TM}$. However, $A_{TM}$ is not decidable, so therefore, $D$ cannot exist.

End of Proof

Where I am confused is how does this show $A_{PTM}$ is not BPP-Complete? As an acceptance problem, I would think $A_{PTM}$ is BPP-Hard, but I don't see how this shows it is not in BPP.


To show that a language is not BPP-complete, it suffices to do one of the following:

  • Show that the language is not in BPP.

  • Show that the language is not BPP-hard.

Your language seems to be undecidable, and so in particular, not in BPP.

  • $\begingroup$ So a BPP-hard language can be undecidable? $\endgroup$ – tpm900 May 3 '17 at 17:31
  • $\begingroup$ Yes, there is no reason why not. Perhaps you can even find an example. $\endgroup$ – Yuval Filmus May 3 '17 at 17:34
  • $\begingroup$ Isn't $A_{PTM}$ a BPP-hard language? $\endgroup$ – tpm900 May 3 '17 at 17:34
  • $\begingroup$ That's a nice question for you to ponder. $\endgroup$ – Yuval Filmus May 3 '17 at 17:37
  • $\begingroup$ If a language is in BPP then it is decided by a PTM with at least a 2/3 acceptance probability, so any BPP language can be reduced to $A_{PTM}$ because $A_{PTM}$ simply simulates a PTM and outputs accept if it accepts. Am I heading in the right direction here? $\endgroup$ – tpm900 May 3 '17 at 17:50

Your Answer

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

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