Perché questo non mette $ bpp $ in $ np $?
Domanda
Da SIPSER GACS conosciamo $ x in l (m) $ per una macchina $ m in bpp $ $ iff $ $$ esiste t_1, dots, t_ {| r |} forall r in {0 , 1 }^{| r |} vee_ {i in {1, dots, | r | }} m (x, r oplus t_i) = 1. $$
Da adleman conosciamo $ x in l (m) $ per una macchina $ m in bpp $ $ $ iff $ $$ esiste r in {0,1 }^{| r |} m (x, r) = 1. $$
Perché questo è solo $ bpp sottoseteq p/poli $ (sembra una derendomizzazione a $ bpp sottoseteq np $)? Se il teorema di Adleman mette solo $ bpp sottoseteq p/poli $ (perché dobbiamo trovare $ r $), allora perché non posso discutere per ragioni simili GAC SIPSER POSSO solo $ bpp sottoseteq conp/poli $ (perché dobbiamo trovare $ t_1, dots, t_ {| r |} $)?
Come avrebbe dovuto sembrare il teorema di Adleman se avesse davvero mostrato $ bpp sottoseteq np $ e come sarebbe stato il teorema di Sipser GACS se avesse mostrato effettivamente $ bpp sottoseteq conp/poli $?
Nessuna soluzione corretta