Schwarz-Zippel Lemma

Schwartzovo-Zippelovo lemma (také DeMillo -Lipton-Schwartz-Sippelovo lemma ) je výsledek široce používaný při kontrole rovnosti polynomů , tedy v problému kontroly nějakého polynomu mnoha proměnných pro shodnou rovnost na nulu. Lema nezávisle na sobě objevili Jack Schwartz [1] , Richard Zippel [2] a Richard DeMillo a Richard Lipton , ačkoli verze DeMilla a Liptona předchází Schwartzův a Zippelův výsledek [3] o rok . Verzi lemmatu pro konečná pole dokázal Oistin Ore v roce 1922 [4] .

Lemma

Vstupem problému je polynom v proměnných nad polem . Může být uveden ve formě aritmetického schématu nebo jako determinant nějaké matice polynomů . V tuto chvíli nejsou známy žádné deterministické subexponenciální algoritmy, které by vám umožnily zkontrolovat, že tento polynom je nenulový. Jsou však známy randomizované algoritmy, které řeší tento problém v polynomiálním čase. Při jejich analýze je obvykle nutné odhadnout pravděpodobnost, že nenulový polynom bude v nějakém náhodně zvoleném bodě roven nule. Schwartz-Zippelovo lemma je formulováno takto: $n$ $\mathbb {F}$

Dovolit být nenulový stupeň polynom nad polem . Nechť je konečná podmnožina a prvky nechť jsou vybírány z jednotně a nezávisle na sobě. Pak . $P\in F[x_{1},x_{2},\dots ,x_{n}]$ $d\geq 0$ $\mathbb {F}$ $S$ $\mathbb {F}$ $r_{1},r_{2},\tečky ,r_{n}$ $S$ $\Pr[P(r_{1},r_{2},\tečky ,r_{n})=0]\leq {\frac {d}{\vert S\vert }}$

Důkaz

V případě jedné proměnné vyplývá lemma přímo z toho, že polynom stupně může mít nanejvýš různé kořeny nad polem . $d$ $d$ $\mathbb {F}$

Lema lze v obecné podobě dokázat matematickou indukcí počtu proměnných . Základní případ byl prokázán výše. $n$ $n=1$

Nechť nyní věta platí pro všechny polynomy na proměnných. Lze jej považovat za polynom v , zapsaný ve tvaru $n-1$ $P$ $x_{1}$

P(x_{1},\tečky ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\ tečky ,x_{n})

Protože se stejně nerovná nule, existuje nějaké číslo , které se také nerovná nule. Nechť je největší z těchto čísel. Poté , protože stupeň nepřesahuje . $P$ $i$ $P_{i}$ $i$ $\deg P_{i}\leq di$ ${\displaystyle x_{1}^{i}P_{i))$ $d$

Nechť být nyní vybrán náhodně z . Podle indukční hypotézy, . ${\displaystyle r_{2},\tečky ,r_{n))$ $S$ $\Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {di}{|S|}}$

Jestliže , pak má stupeň (a proto se nerovná nule shodně), proto $P_{i}(r_{2},\ldots ,r_{n})\neq 0$ $P(x_{1},r_{2},\ldots ,r_{n})$ $i$

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

Pokud událost označíme jako , událost jako a navíc k události jako , pak $P(r_{1},r_{2},\ldots ,r_{n})=0$ $A$ $P_{i}(r_{2},\ldots ,r_{n})=0$ $B$ $B$ $B^{c}$

{\begin{aligned}\Pr[A]&=\Pr[A\cap B]+\Pr[A\cap B^{c}]\\&=\Pr[B]\Pr[A |B]+\Pr[B^{c}]\Pr[A|B^{c}]\\&\leq \Pr[B]+\Pr[A|B^{c}]\\&\ leq {\frac {di}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}\end{aligned}}

■

Aplikace

Význam Schwarz-Sippelova lemmatu a ověření rovnosti polynomů vyplývá z algoritmů, které lze redukovat na tento problém.

Porovnání dvou polynomů

Vzhledem ke dvěma polynomům a , je to pravda $p_{1}(x)$ $p_{2}(x)$

p_{1}(x)\equiv p_{2}(x)?

Tento problém lze zredukovat na kontrolu rovnosti polynomů, protože to stačí zkontrolovat

[p_{1}(x)-p_{2}(x)]\equiv 0.

Pokud je to tedy možné určit

p(x)\equiv 0,

kde

p(x)=p_{1}(x)\;-\;p_{2}(x),

pak je také možné určit, zda jsou dané dva polynomy stejné.

Srovnání dvou polynomů lze použít při analýze rozvětvených programů . Jednou přečtený větvený program může být reprezentován jako multilineární polynom , který vyhodnocuje (přes nějaké pole) od nul a jedniček stejnou booleovskou funkci jako větvící program. Dva větvené programy tedy vyhodnocují stejnou booleovskou funkci právě tehdy, když jsou odpovídající polynomy stejné. To znamená, že kontrolu rovnosti booleovských funkcí, které jsou počítány programy pro jednorázové čtení s větvením, lze omezit na kontrolu rovnosti polynomů.

Test jednoduchosti

Je dané číslo prvočíslo ? $n\in \mathbb {Z^{+}}$ $n$

Manindra Agrawal a Somenath Biswas vyvinuli jednoduchý randomizovaný algoritmus používající testy polynomiální rovnosti k určení, zda je číslo prvočíslo . $n$

Ukázali, že všechna prvočísla (a pouze prvočísla) vyhovují následujícímu srovnání: $n$

(1+z)^{n}=1+z^{n}({\mbox{mod}}\;n).

Tento výsledek vyplývá z Frobenius endomorphism .

Nechat

{\mathcal {P}}_{n}(z)=(1+z)^{n}-1-z^{n}.

Pak právě tehdy, když je prvočíslo [5] . Protože se však může a nemusí jednat o prvočíslo, metoda Schwartz-Zippel zde nebude fungovat. Agrawal a Biswas používají sofistikovanější techniku, která zahrnuje dělení náhodným redukovaným polynomem malého stupně. ${\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)$ $n$ $n$ ${\mathcal {P}}_{n}$

Dokonalá shoda

Daný graf na $G=(V,E)$ vrcholech, kde je sudé číslo. Obsahuje dokonalou shodu ? $n$ $n$ $G$

Determinant Tuttovy matice není identicky nulový polynom , a to pouze tehdy, pokud má graf dokonalou shodu.

( Tutte 1947 )

Podmnožina množiny hran se nazývá shoda, pokud každý vrchol z je incidentní s nejvýše jednou hranou z . Shoda se nazývá dokonalá, pokud každý vrchol je incidentní s přesně jednou hranou . Matta Tatta je matrice: $D$ $E$ $PROTI$ $D$ $PROTI$ $D$ $A$

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1{\mathit {n))}\\a_{21}&a_{22}&\cdots &a_{2{ \mathit {n}}}\\\vdots &\vdots &\ddots &\vdots \\a_{{\mathit {n}}1}&a_{{\mathit {n}}2}&\ldots &a_{\ mathit {nn}}\end{bmatrix}}

kde

a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\v E{\mbox{ a }}i<j\ \-x_{ji}\;\;{\mbox{if}}\;(i,j)\v E{\mbox{ a }}i>j\\0\;\;\;\;{\ mbox{jinak}}.\end{cases}}

Determinant Tuttovy matice (jako polynom v ) je dán jako determinant této šikmo symetrické matice , která se rovná druhé mocnině Pfaffova matice a je nenulová shodně právě tehdy, když existuje dokonalá shoda v graf. $x_{ij},i<j$ $A$

Pomocí testu polynomiální rovnosti lze tedy zkontrolovat, zda libovolný graf obsahuje dokonalou shodu. $G$

Ve speciálním případě vyváženého bipartitního grafu ve vrcholech má matice Tatta formu blokové matice $n=m+m$

A={\begin{pmatrix}0&X\\-X^{t}&0\end{pmatrix}}

První řádky (a v souladu s tím i sloupce) jsou indexovány první částí bipartitního grafu a poslední řádky jsou indexovány druhou částí. V tomto případě se Pfaffian (až znaménko) shoduje s obvyklým determinantem matice velikosti . Matice je pak Edmondsova matice daného bipartitního grafu. $m$ $m$ $X$ $m \krát m$ $X$

Poznámky

↑ ( Schwartz 1980 )
↑ ( Zippel 1979 )
↑ ( DeMillo & Lipton 1978 )
↑ Ö. Ore, Über höhere Kongruenzen. norská podložka. Forenings Skrifter Ser. I (1922), č.p. 7, 15 stran.
↑ ( Agrawal 2003 )

Literatura

Agrawal, Manindra; Biswas, Somenath. Testování primality a identity prostřednictvím čínského zbytku // Journal of the ACM : journal. - 2003. - Sv. 50 , č. 4 . - str. 429-443 . - doi : 10.1145/792538.792540 .
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech O složitosti porovnávání vzorů pro vysoce komprimované dvourozměrné texty // Journal of Computer and System Sciences : deník. - 2002. - Sv. 65 , č. 2 . - S. 332-350 . - doi : 10.1006/jcss.2002.1852 .
Grigorjev, Dima; Karpinski, Marek. Problém shody pro bipartitní grafy s polynomiálně ohraničenými permanenty je v NC . - 1987. - S. 166-172. - ISBN 978-0-8186-0807-0 . - doi : 10.1109/SFCS.1987.56 .
Moshkovitz, Dana (2010). Alternativní důkaz Schwartz-Zippelova lemmatu.
DeMillo, Richard A.; Lipton, Richard J.Pravděpodobnostní poznámka k testování algebraických programů // Information Processing Letters : deník. - 1978. - Sv. 7 . - S. 193-195 . - doi : 10.1016/0020-0190(78)90067-4 .
Rudich, Steven. Teorie výpočetní složitosti (neopr.) / AMS. - 2004. - V. 10. - (IAS / Matematická řada Park City). - ISBN 978-0-8218-2872-4 .
Schwartz, Jacku Rychlé pravděpodobnostní algoritmy pro ověřování polynomiálních identit (anglicky) // Journal of the ACM : journal. - 1980. - říjen ( roč. 27 , č. 4 ). - str. 701-717 . - doi : 10.1145/322217.322225 .
Tutte, W.T. Faktorizace lineárních grafů (neurčitá) // J. London Math. Soc.. - 1947. - Duben ( roč. 22 , č. 2 ). - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .
Zippel, Richard. Pravděpodobnostní algoritmy pro řídké polynomy . - 1979. - Sv. 72. - S. 216-226. — ISBN 978-3-540-09519-4 . - doi : 10.1007/3-540-09519-5_73 .
Zippel, Richard Explicitní oddělení relativizovaného náhodného polynomiálního času a relativizovaného deterministického polynomického času (ps) (únor 1989). Staženo: 15. června 2008. (neurčitý)
Zippel, Richard. Efektivní polynomiální výpočet (neopr.) / Springer. - 1993. - T. 241. - (The Springer International Series in Engineering and Computer Science). - ISBN 978-0-7923-9375-7 .

Odkazy

Podivuhodná historie lemmatu Schwartz-Zippel , Richard J. Lipton