1
$\begingroup$

Does every language $C$ in the class $BPP$ have a mapping reduction to $A_{TM}$? $(C\leq _{m} A_{TM})$

$BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $\epsilon$ less than 1/3.

$A_{TM}$ is the acceptance language, takes as input a $TM$ description of $M$ and a word w, then determines if w is in $M$'s langugae. $A_{TM}$ is of course undecidable!

$\endgroup$
1
  • $\begingroup$ Note BPP is a subset of EXP. $\endgroup$
    – xskxzr
    Commented Mar 15, 2018 at 9:06

1 Answer 1

2
$\begingroup$

Yes.

Every decidable language reduces to $A_{\mathrm{TM}}$.

Every language in BPP is decidable because the definition requires that every execution of the probabilistic machine halts in polynomial time. So you can just simulate out all the possibilities and compute the probability that the machine accepts.

$\endgroup$
2
  • $\begingroup$ If you can only clarify on why is it so, that every decidable language reduces to ATM? Is it because decidable languages have smaller time complexity than ATM? Thank you. $\endgroup$ Commented Mar 16, 2018 at 1:45
  • $\begingroup$ A $L$ language is decidable if ______. A string $x$ is in $L$ if ______. Now relate that to the definition of $A_{\mathrm{TM}}$. $\endgroup$ Commented Mar 16, 2018 at 10:47

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.