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$
  • $\begingroup$ Note BPP is a subset of EXP. $\endgroup$ – xskxzr Mar 15 '18 at 9:06
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$
  • $\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$ – Anwar Saiah Mar 16 '18 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$ – David Richerby Mar 16 '18 at 10:47

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.