Încerc ca autodidact să citesc capitolul 4 din Foundation of Cryptography de Oded Goldreich (doar ca să vă las să vă „ajustați” răspunsurile, am experiență de inginerie).
Dacă am înțeles corect, oferind un simulator perfect $S_1$ posibilitatea de a opri nu este o problemă deoarece putem defini un simulator $S_2$ care se repetă $S_1$ sa spunem $n$ ori, afișând rezultatul primei ne-oprire $S_1$ iterație, sau un rezultat „fictiv” dacă ALL $S_1$ iterațiile se opresc. În acest fel probabilitatea de $S_2$ ieșirea rezultatului inactiv poate fi redusă după cum doriți cu creșterea $n$.
$S_1$ probabilitatea de oprire este delimitată mai sus de $1/2$, dar de ce? Mi se pare că fiecare $S_1$ probabilitatea de oprire $<1$ va fi coborât spre $0$ de un suficient de mare $n$. Mai mult, cel al simulatorului pare un argument foarte diferit de probabilitățile de completitudine/soliditate, unde strict $1/2$ pragul este justificat de regula majorității aplicată acelei (diferite) strategii de repetiții.
Și, btw, există vreun motiv de a alege $S_1$ valoarea repetărilor $n$ să fie același cu numărul celorlalte repetări necesare pentru a trece de la completitudine/corectitudine slabă la cele mai puternice? Sau numerele celor două tipuri de iterații sunt reciproc independente? Bănuiesc că această îndoială vine din cauza faptului că sunt confuz cu privire la dacă $S_2$ este simulatorul pentru IP slab sau pentru IP mai puternic...
Mulțumiri!
