1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please define the language $A_{PTM}$, what exactly are the strings in the language. $\endgroup$ – Ariel May 3 '17 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 May 3 '17 at 18:25
  • $\begingroup$ If $M$ is probabilistic, what does it mean for $M$ to accept $x$? $\endgroup$ – Ariel May 3 '17 at 18:26
  • $\begingroup$ @Ariel it means $M$ accepts $x$ with an error probability $\endgroup$ – tpm900 May 3 '17 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 May 3 '17 at 18:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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