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

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?

• Please define the language $A_{PTM}$, what exactly are the strings in the language. May 3, 2017 at 18:17
• @Ariel I added the definition of $A_{PTM}$. It is the language consisting of elements that are a pair of a PTM and a string, such that the PTM accepts the string. May 3, 2017 at 18:25
• If $M$ is probabilistic, what does it mean for $M$ to accept $x$? May 3, 2017 at 18:26
• @Ariel it means $M$ accepts $x$ with an error probability May 3, 2017 at 18:27
• @Ariel if $A_{TM} \le_m A_{PTM}$ then the error probability of a regular TM would be 0 May 3, 2017 at 18:28

First, $A_{PTM}$ as you defined it is not even decidable (so it isn't in BPP), since your simulation might not halt.
$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.