Zaawansowane algorytmy i struktury danych/Ćwiczenia 15

Zadanie 1

Udowodnij lemat Zuppela-Schwartca podany poniżej.

Lemat [Zippela-Schwartza]

Niech $p(x_{1},\ldots ,x_{n})$ będzie niezerowym wielomianem $n$ zmiennych stopnia $d$ nad ciałem $F$. Niech $S$ będzie skończonym podzbiorem $F$ oraz niech $r_{1},\ldots ,r_{n}$ będą losowymi elementami z $S$, wtedy:

$\Pr[p(r_{1},\ldots ,r_{n})=0]\leq {\frac {d}{|S|}}.$

Rozwiązanie

Dowód

Dowód lematu przeprowadzimy przez indukcję po $n$. Dla $n=1$ wielomian $p$ może mieć co najwyżej $d$ zer, co daje podstawę indukcji. Załóżmy teraz, że lemat ten zachodzi dla wszystkich wielomianów nad $n-1$ zmiennymi. Możemy wtedy zapisać $p$ jako wielomian $x_{1}$:

$p(x_{1},\ldots ,x_{n})=\sum _{i=0}^{d}x_{i}^{d}p_{i}(x_{2},\ldots ,x_{n}).$

Ponieważ $p$ nie jest zerowy, to istnieje takie $i$ dla którego $p_{i}$ nie jest zerowy. Weźmy największe takie $i$. Wtedy $\deg p_{i}\leq d-i$. Wybierzmy teraz losowo elementy $r_{2},\ldots ,r_{n}$ z $S$. Z hipotezy indukcyjnej mamy:

$\Pr[p_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {d-i}{|S|}}.$

Jeżeli $p_{i}(r_{2},\ldots ,r_{n})\neq 0$, to wtedy $p(x_{1},r_{2},\ldots ,r_{n})$ ma stopień $i$, a więc

$\Pr[p(r_{1},r_{2},\ldots ,r_{n})=0|P_{i}(r_{2},\ldots ,r_{n})\neq 0]\leq {\frac {i}{|S|}}.$

Mamy więc:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{r@{}c@{}l} \Pr[p(r_1,r_2,\ldots,r_n)=0] &=&\\ &=& \Pr[P_i(r_2,\ldots,r_n) = 0] \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) = 0] +\\&+& \Pr[P_i(r_2,\ldots,r_n) \neq 0] \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) \neq 0]\le\\ &\le& \Pr[P_i(r_2,\ldots,r_n) = 0] + \Pr[p(r_1,r_2,\ldots,r_n)=0 | P_i(r_2,\ldots,r_n) \neq 0] \le\\ &\le& \frac{d-i}{|S|} + \frac{i}{|S|} = \frac{d}{|S|}. \end{array} }

Zadanie 2

Masz daną formułę logiczną w postaci DNF. Zaproponuj efektywny algorytm losowego generowania z rozkładem jednostajnym wartościowań ją spełniających?

Rozwiązanie

Zadanie 3

Rozwiązanie