0
$\begingroup$

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 Proof

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So a BPP-hard language can be undecidable? $\endgroup$
    – tpm900
    Commented May 3, 2017 at 17:31
  • $\begingroup$ Yes, there is no reason why not. Perhaps you can even find an example. $\endgroup$
    – Yuval Filmus
    Commented May 3, 2017 at 17:34
  • $\begingroup$ Isn't $A_{PTM}$ a BPP-hard language? $\endgroup$
    – tpm900
    Commented May 3, 2017 at 17:34
  • $\begingroup$ That's a nice question for you to ponder. $\endgroup$
    – Yuval Filmus
    Commented May 3, 2017 at 17:37
  • $\begingroup$ If a language is in BPP then it is decided by a PTM with at least a 2/3 acceptance probability, so any BPP language can be reduced to $A_{PTM}$ because $A_{PTM}$ simply simulates a PTM and outputs accept if it accepts. Am I heading in the right direction here? $\endgroup$
    – tpm900
    Commented May 3, 2017 at 17:50

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.