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
scroll top