- functie neglijabila
- f : N → R este neglijabila ⇔ ∀ c > 0, ∃ kc, ai f(k) < k-c, ∀ k > kc
- functie puternica cu sens unic
- f : {0, 1}* → {0, 1}* este puternica, cu sens unic ⇔:
- ∃ A, un algoritm PTP (probabilstic de timp polinomial), care obtine y = f(x), pentru x dat
- ∀ A, ∃ mA, o functie neglijabila, ai P [ f ( z ) = y ; x ∈ {0, 1}* ; y ← f ( x ) ; z ← A ( y ) ] ≦ mA pentru k suficient de mare
Garantia este probilista, distributia de probabilitate este pe intreg domeniul lui f; nu se cere sa determine x ci sa se gaseasca o inversa ptr y; algoritmul primeste ca intrare f ( x ) si ruleaza in timp polinomial pe |x| - functie slaba cu sens unic
- f : {0, 1}* → {0, 1}* este slaba, cu sens unic ⇔:
- ∃ A, un algoritm PTP, care obtine y = f(x), pentru x dat
- ∀ A, ∃ Q, o functie polinomiala, ai P [ f ( z ) ≠ y ; x ∈ {0, 1}* ; y ← f ( x ) ; z ← A ( y ) ] ≧ mA pentru k suficient de mare
Diferenta intre cele tipuri de functii este ca o functie slaba cu sens unic este greu de inversat pe o fractiune neglijabila a domeniului in timp ce o functie puternica cu sens unic este greu de inversat pe tot domeniul mai putin o fractiune neglijabila
∃ functii slabe ⇔ ∃ functii puternice - familie de functii puternice cu sens unic
- F = { fi : Di → Ri }i∈I, unde i ∈ I, ,multimea indicilor, este o familie de functii puternice cu sens unic daca:
- ∃ S1, un algoritm PTP, ai i ← S1 ( x ∈ {0, 1}k ), i∈ {0, 1}k ∩ I
- ∃ S2, un algoritm PTP, ai x ← S2 ( i ∈ I ), x∈ Di
- ∃ A1, un algoritm PTP, ai A1 ( i , x ) = fi( x ), unde i ∈ I, x ∈ Di
- ∀ A, un algoritm PTP, ∃ mA, o functie neglijabila, ai P [ fi ( z ) = y ; x ∈ Di; i ∈ I ; y ← fi ( x ) ; z ← A ( i , y ) ] ≦ mA pentru k suficient de mare
probabilitatea este luata peste alegerile lui i si x pentru A echiprobabil
∃ o familie de functii puternice cu sens unic ⇔ ∃ functii puternice
# posted by Sorin Badescu @ 4:46 PM
