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 ProofWhere 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.
Prove a language $A_{PTM}$ is not BPP-Complete
turing machines;proof techniques;probability theory
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.