Is $A_{PTM}$ a BPP-complete language?

Question

The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.

$A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/3}

Basically, given a probabilistic Turing machine $P$ and string $x$, a decider $D$ simulates $P$ on $x$ and outputs accept if $P$ accepts on $x$, and rejects otherwise.

I claim $A_{PTM}$ is BPP-hard because BPP is the class of languages which are accepted a success probability of at least $2/3$. If the PTM for any BPP language is given as an argument to the decider $D$, then it will output accept if the PTM it was passed accepts, and reject otherwise. I know this is far from a formal proof, but I am just trying to understand the idea. Is this correct?

Answer 1

First, $A_{PTM}$ as you defined it is not even decidable (so it isn't in BPP), since your simulation might not halt.

The naive attempt at a BPP complete language is:

$A_{PTM}=\left\{\left(\langle M\rangle,x, 1^t\right) \big| M \text{ accepts $x$ in $\le t$ steps with probability $\ge \frac{2}{3}$} \right\}$.

Note that there is no notion of "error" in the definition of $A_{PTM}$, as there are no right answers, you decide whether or not to include some triplet in your language.

You can show that $A_{PTM}$ is indeed BPP-hard (I leave the reduction details for you). The problem is that we do not know if $A_{PTM}\in \mathsf{BPP}$. Simply simulating $M$ on $x$ for $t$ steps and outputing its answer won't work. Imagine $M$ accepts $x$ after $t$ steps with probability $\frac{1}{2}$, then although $(M,x,t)\notin A_{PTM}$, you accept it with probability $\frac{1}{2}$, while you should be accepting with probability $\le \frac{1}{3}$.

In fact, $A_{PTM}$ is $\mathsf{PP}$ complete, so it is unlikely to lie in $\mathsf{BPP}$. The existence of complete problems for BPP is currently an open question in complexity. You can check this question from cs-theory, which talks about why it is harder to find complete problems for classes like BPP.