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?

  • $\begingroup$ Please define the language $A_{PTM}$, what exactly are the strings in the language. $\endgroup$
    – Ariel
    Commented May 3, 2017 at 18:17
  • $\begingroup$ @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. $\endgroup$
    – tpm900
    Commented May 3, 2017 at 18:25
  • $\begingroup$ If $M$ is probabilistic, what does it mean for $M$ to accept $x$? $\endgroup$
    – Ariel
    Commented May 3, 2017 at 18:26
  • $\begingroup$ @Ariel it means $M$ accepts $x$ with an error probability $\endgroup$
    – tpm900
    Commented May 3, 2017 at 18:27
  • $\begingroup$ @Ariel if $A_{TM} \le_m A_{PTM}$ then the error probability of a regular TM would be 0 $\endgroup$
    – tpm900
    Commented May 3, 2017 at 18:28

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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