Doua lucruri:
Da, $x_1$ este primul bit. Ideea este că dacă $x_1 = 0$ (care apare cu probabilitatea 1/2), este simplu să găsiți o preimagine a $g(x) = 0$ --- orice șir $x'$ cu $x'_1 = 0$ va fi de ajuns. Asta arată că $g$ nu poate fi un $\alpha$-OWF pentru orice $\alpha <1/2$. Pentru a arăta că este o $\alpha$-OWF pentru $\alpha \leq 2/3$, ar trebui să reduceți la securitatea puternică OWF a $f$, ceea ce vă las să faceți.
Alegerea de $2/3$ este pur și simplu o convenție socială pentru o „constantă potrivită”. Sunt mulți clase de complexitate $\mathcal{C}$ care depind de un anumit parametru $\alpha$ (pe care o voi nota $\mathcal{C}(\alpha)$) unde puteți afișa un rezultat al formularului
Pentru orice $\alpha$ mărginit departe* de $1/2$ și $1$, clasele de complexitate $\mathcal{C}(\alpha)$ sunt echivalente.
Aici, „delimitat departe” înseamnă asta $\frac{1}{2}+\frac{1}{n^c} \leq \alpha \leq 1 - \frac{1}{n^d}$ pentru constante $c, d$ --- în special, $\alpha$ nu poate fi neglijabil apropiat (în funcție de mărimea intrării) fie de 1/2, fie de 1. Pentru astfel de clase, convenția socială de a alege $\mathcal{C}(2/3)$ deoarece exemplul „standard” cu care se relaționează lucrurile este obișnuit.
Există multe exemple ale fenomenului de mai sus, de exemplu cele mai multe clase de complexitate randomizate, dar poate $BPP$ în special este cel mai cunoscut exemplu.
Importanta $\alpha$ fiind delimitat de 1/2 și 1 poate fi văzut prin diferența dintre clase $BPP$ (care are această restricție) și clasa $PP$ (care nu, și este mult mai puternic).
Oricum, această secțiune a notelor legate arată în esență că funcțiile unidirecționale sunt o clasă similară cu lucruri precum $BPP$ (în ceea ce privește dependența lor de un parametru $\alpha$).
