Pergunta

From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$

From Adleman we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists r\in\{0,1\}^{|r|}M(x,r)=1.$$

  1. Why is this just $BPP\subseteq P/Poly$ (looks like a derandomization to $BPP\subseteq NP$)? If Adleman's theorem just puts $BPP\subseteq P/Poly$ (because we need to find $r$) then why cannot I argue for similar reasons Sipser Gacs only puts $BPP\subseteq coNP/Poly$ (because we need to find $t_1,\dots,t_{|r|}$)?

  2. What should Adleman's theorem have looked like if it indeed showed $BPP\subseteq NP$ and what should Sipser Gacs' theorem have looked like if it indeed showed $BPP\subseteq coNP/poly$?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top