Puncte:0

PRG implică OWF Proof

drapel lk

introduceți descrierea imaginii aici Mi-am dat ideea acestei dovezi, că, deoarece PRG se extinde de la n la 2n, nu poate proiecta la toți {0,1}^{2n}, doar la o parte neglijabilă de care putem abuza pentru a face un bun deosebitor doar spunând dacă A reușește să găsească o preimagine în X. Un șir aleatoriu din U2n are foarte probabil să nu aibă preimagine în X. Astfel, putem distinge U2n de G(Un). Dar cred că nu înțeleg bine construcția f. Care este scopul y-ului nostru? Nu putem demonstra acest lucru folosind f(x) := G(x)? De asemenea, de ce este f variabilă? Dacă definim f așa, nu ar trebui să fie o proiecție de la 2n la 2n? Mi-e dor de ceva.

drapel cn
Definiția unui OWF folosit acolo probabil necesită ca funcția să fie conservarea lungimii. Deoarece G se extinde, trebuie să completați intrarea.
killertoge avatar
drapel lk
Ok, asta are sens. Am sărit înapoi la pagina 40: „În continuare, ne vom ocupa doar de funcții unidirecționale care sunt regulate în funcție de lungime [...] în principal cu funcții de păstrare a lungimii”. Folosesc cartea lui Goldreich pentru a citi dovezi despre care prelegerea noastră nu vorbește, așa că ar trebui să fiu mai atent. Mulțumiri.
kodlu avatar
drapel sa
Întrebarea ta este greu de citit. Vă rugăm să folosiți Mathjax
killertoge avatar
drapel lk
@kodlu Învăț puțin Latex în prezent, cu siguranță voi încerca să-l folosesc la următoarea întrebare.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.