# Prove a language $A_{PTM}$ is not BPP-Complete

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.

• So a BPP-hard language can be undecidable? – tpm900 May 3 '17 at 17:31
• Yes, there is no reason why not. Perhaps you can even find an example. – Yuval Filmus May 3 '17 at 17:34
• Isn't $A_{PTM}$ a BPP-hard language? – tpm900 May 3 '17 at 17:34
• That's a nice question for you to ponder. – Yuval Filmus May 3 '17 at 17:37
• 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? – tpm900 May 3 '17 at 17:50