Does every language in BPP have a mapping reduction to ATM?
-
05-11-2019 - |
Pergunta
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!
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange