- functie cu trapa
- f : N → R este o functie cu trapa ⇔
- f este o functie cu sens unic
- ∃ p, o functie polinomiala, si ∃ A, un algoritm PTP ai
- ∀ k, ∃ tk ∈ {0, 1}* cu | tk | ≦ p ( k )
- ∀ x ∈ {0, 1}*, A( f ( x) , tk) = y ai f ( y ) = f ( x)
- familie de functii puternice cu trapa si cu sens unic
- F = { fi : Di → Di }i∈I, unde i ∈ I, ,multimea indicilor, este o familie de functii puternice cu trapa si cu sens unic daca:
- ∃ S1, o MTP, si p, o functie polinomiala, ai ( i , ti ) ← S1 ( x ∈ {0, 1}k ), i ∈ {0, 1}k ∩ I si | ti | < p ( k ); ti se numeste trapa pentru i
- ∃ S2, o MTP, ai x ← S2 ( i ∈ I ), x∈ Di
- ∃ A1, o MTP, 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 echiprobabila
# posted by Sorin Badescu @ 3:39 PM