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. $$

  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 |} $)?

  2. 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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top