Questions marquées «randomness»

Y a-t-il eu des tentatives pour montrer que le caractère aléatoire de Kolmogorov serait suffisant pour RP ? La probabilité utilisée dans l'énoncé "Si la bonne réponse est OUI, alors elle (la machine probabiliste de Turing) renvoie OUI avec probabilité ..." serait-elle toujours bien définie dans ce...

Voici deux familles de fonctions de hachage sur les chaînes x⃗ =⟨x0x1x2…xm⟩x→=⟨x0x1x2…xm⟩\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle : pppxi∈Zpxi∈Zpx_i \in \mathbb{Z_p}a ∈ Z p ∀ x ≠ y , P a ( h 1 a ( x ) = h 1 a ( y ) ) ≤ m / ph1a(x⃗ )=∑aiximodpha1(x→)=∑aiximodph^1_{a}(\vec{x}) = \sum a^i x_i...

Étant donné une fonction booléenne , nous avons le groupe d'automorphisme A u t ( f ) = { σ ∈ S n ∣ ∀ x , f ( σ ( x ) ) = f ( x ) } .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Existe-t-il des bornes connues sur ?...