Schwarz-Zippel Lemma

Schwartz- Zippel-lemma (myös DeMillo -Lipton-Schwartz-Sippel-lemma ) on tulos, jota käytetään laajalti polynomien yhtäläisyyden tarkistamisessa , toisin sanoen ongelmassa, jossa monien muuttujien joidenkin polynomien tarkistaminen on identtinen nollan kanssa. Lemman löysivät itsenäisesti Jack Schwartz [1] , Richard Zippel [2] sekä Richard DeMillo ja Richard Lipton , vaikka DeMillon ja Liptonin versio on Schwartzin ja Zippelin tulosta [3] edeltävä vuodella . Oistin Ore osoitti version äärellisten kenttien lemmasta vuonna 1922 [4] .

Lemma

Tehtävän syöte on muuttujien polynomi kentän päällä . Se voidaan antaa aritmeettisena kaaviona tai jonkin polynomimatriisin determinanttina . Tällä hetkellä ei ole tunnettuja deterministisiä osaeksponentiaalisia algoritmeja, joiden avulla voit tarkistaa, että tämä polynomi on nollasta poikkeava. On kuitenkin tunnettuja satunnaistettuja algoritmeja, jotka ratkaisevat tämän ongelman polynomiajassa. Niitä analysoitaessa on yleensä arvioitava todennäköisyys, että nollasta poikkeava polynomi on nolla jossain satunnaisesti valitussa pisteessä. Schwartz-Zippel-lemma on muotoiltu seuraavasti: $n$ $\mathbb {F}$

Antaa olla nollasta poikkeava polynomi kentän päällä . Olkoon äärellinen osajoukko ja valitaan alkiot tasaisesti ja toisistaan riippumatta. Sitten . $P\in F[x_{1},x_{2},\dots ,x_{n}]$ $d\geq 0$ $\mathbb {F}$ $S$ $\mathbb {F}$ $r_{1},r_{2},\dots ,r_{n}$ $S$ $\Pr[P(r_{1},r_{2},\dots ,r_{n})=0]\leq {\frac {d}{\vert S\vert }}$

Todiste

Yhden muuttujan tapauksessa lemma seuraa suoraan siitä, että astepolynomilla voi olla korkeintaan eri juuret kentän yli . $d$ $d$ $\mathbb {F}$

Lemma voidaan todistaa yleisessä muodossa muuttujien lukumäärän matemaattisella induktiolla . Perustapaus todistettiin yllä. $n$ $n = 1$

Olkoon lause nyt totta kaikille muuttujien polynomeille. Sitä voidaan pitää polynomina muodossa , joka on kirjoitettu muotoon $n-1$ $P$ $x_{1}$

P(x_{1},\dots ,x_{n})=\sum _{i=0}^{d}x_{1}^{i}P_{i}(x_{2},\ pisteet ,x_{n})

Koska se ei ole yhtä suuri kuin nolla identtisesti, on olemassa jokin luku , joka ei myöskään ole yhtä suuri kuin nolla. Antaa olla suurin tällaisista luvuista. Sitten , koska aste ei ylitä . $P$ $i$ $P_{i}$ $i$ $\deg P_{i}\leq di$ $x_{1}^{i}P_{i}$ $d$

Olkoon nyt valittu satunnaisesti joukosta . Induktiohypoteesin mukaan . ${\displaystyle r_{2},\dots ,r_{n))$ $S$ $\Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {di}{|S|}}$

Jos , Sitten on aste (ja siksi ei ole sama kuin nolla identtisesti), siksi $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|}}

Jos määritämme tapahtuman nimellä , tapahtumaksi ja tapahtuman lisäksi nimellä , niin $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}}

■

Sovellukset

Schwarz-Sippel-lemman merkitys ja polynomien yhtäläisyyden todentaminen seuraa algoritmeista, jotka voidaan pelkistää tähän ongelmaan.

Kahden polynomin vertailu

Koska kaksi polynomia ja Onko totta, että $p_{1}(x)$ $p_{2}(x)$

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

Tämä ongelma voidaan lyhentää polynomien yhtäläisyyden tarkistamiseen, koska sen tarkistaminen riittää

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

Joten jos se on mahdollista määrittää

p(x)\equiv 0,

missä

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

silloin on myös mahdollista määrittää, ovatko annetut kaksi polynomia yhtä suuret.

Kahden polynomin vertailua voidaan käyttää haaroittuneiden ohjelmien analysoinnissa . Kerran luettava haaroitusohjelma voidaan esittää monilineaarisena polynomina , joka arvioi (jonkin kentän yli) nollista ja ykkösistä saman Boolen funktion kuin haaraohjelma. Näin ollen kaksi haaraohjelmaa arvioivat saman Boolen funktion silloin ja vain, jos vastaavat polynomit ovat yhtä suuret. Tämä tarkoittaa, että haaroituksella varustetuilla ohjelmilla laskettujen Boolen funktioiden yhtäläisyyden tarkistaminen voidaan pelkistää polynomien yhtäläisyyden tarkistamiseksi.

Yksinkertaisuustesti

Annettu luku , onko se alkuluku ? $n\in \mathbb {Z^{+}}$ $n$

Manindra Agrawal ja Somenath Biswas kehittivät yksinkertaisen satunnaistetun algoritmin käyttämällä polynomiyhtälisyystestejä sen määrittämiseksi, onko luku alkuluku . $n$

He osoittivat, että kaikki alkuluvut (ja vain alkuluvut) täyttävät seuraavan vertailun: $n$

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

Tämä tulos johtuu Frobeniuksen endomorfismista .

Päästää

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

Sitten jos ja vain jos on alkuluku [5] . Koska se voi kuitenkin olla alkuluku tai ei, Schwartz-Zippel-menetelmä ei toimi tässä. Agrawal ja Biswa käyttävät kehittyneempää tekniikkaa, joka sisältää jakamisen pienen asteen satunnaisella pelkistetyllä polynomilla . ${\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)$ $n$ $n$ ${\mathcal {P}}_{n}$

Täydellinen yhteensopivuus

Annettu graafi pisteistä $G=(V,E)$ , jossa on parillinen luku. Sisältääkö se täydellisen yhteensovituksen ? $n$ $n$ $G$

Tutt-matriisin determinantti ei ole identtinen nollapolynomi , jos ja vain jos graafilla on täydellinen vastaavuus.

( Tutte 1947 )

Reunajoukon osajoukkoa kutsutaan sovitukseksi, jos jokainen kärki osoitteesta on sattuma enintään yhden reunan kanssa . Täsmäystä kutsutaan täydelliseksi, jos jokainen pisteen kärki kohtaa täsmälleen yhden reunan kanssa . Tatta -matriisi on matriisi: $D$ $E$ $V$ $D$ $V$ $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}}

missä

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

Tutt-matriisin determinantti (polynomina kohdassa ) on annettu tämän vinosymmetrisen matriisin determinantiksi , joka on yhtä suuri kuin matriisin Pfaffian neliö ja on nollasta poikkeava identtisesti, jos ja vain jos siinä on täydellinen vastaavuus. kaavio. $x_{ij},i<j$ $A$

Näin ollen polynomin yhtäläisyystestin avulla voidaan tarkistaa, sisältääkö mielivaltainen graafi täydellisen vastaavuuden. $G$

Tasapainotetun kaksiosaisen graafin pisteissä erikoistapauksessa Tatta-matriisi on lohkomatriisin muodossa ${\näyttötyyli n=m+m}$

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

Ensimmäiset rivit (ja vastaavasti sarakkeet) indeksoidaan kaksiosaisen kaavion ensimmäisellä osalla, ja viimeiset rivit indeksoidaan toisella osalla. Tässä tapauksessa Pfaffian (merkkiin asti) on sama kuin kokomatriisin tavallinen determinantti . Matriisi on tällöin annetun kaksiosaisen graafin Edmonds-matriisi . $m$ $m$ $X$ $m \ kertaa m$ $X$

Muistiinpanot

↑ ( Schwartz 1980 )
↑ ( Zippel 1979 )
↑ ( DeMillo & Lipton 1978 )
↑ Ö. Ore, Über höhere Kongruenzen. norsk matto. Forenings Skrifter Ser. I (1922), nro. 7, 15 sivua.
↑ ( Agrawal 2003 )

Kirjallisuus

Agrawal, Manindra; Biswas, Somenath. Primaalisuuden ja identiteetin testaus kiinan lopun kautta // Journal of the ACM : Journal. - 2003. - Voi. 50 , ei. 4 . - s. 429-443 . - doi : 10.1145/792538.792540 .
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech Erittäin pakatun kaksiulotteisen tekstin kuvioiden sovittamisen monimutkaisuudesta // Journal of Computer and System Sciences : päiväkirja. - 2002. - Voi. 65 , no. 2 . - s. 332-350 . - doi : 10.1006/jcss.2002.1852 .
Grigorjev, Dima; Karpinski, Marek. Kaksiosaisten graafien yhteensopivuusongelma polynomirajoitteisilla pysyvillä on NC . - 1987. - s. 166-172. - ISBN 978-0-8186-0807-0 . - doi : 10.1109/SFCS.1987.56 .
Moshkovitz, Dana (2010). Vaihtoehtoinen todiste Schwartz-Zippel-lemmasta.
DeMillo, Richard A.; Lipton, Richard J.Todennäköisyyspohjainen huomautus algebrallisten ohjelmien testauksesta // Information Processing Letters : päiväkirja. - 1978. - Voi. 7 . - s. 193-195 . - doi : 10.1016/0020-0190(78)90067-4 .
Rudich, Steven. Laskennallinen monimutkaisuusteoria (neopr.) / AMS. - 2004. - V. 10. - (IAS / Park City Mathematics Series). - ISBN 978-0-8218-2872-4 .
Schwartz, Jack Nopeat todennäköisyyspohjaiset algoritmit polynomisten identiteettien tarkistamiseen (englanniksi) // Journal of the ACM : Journal. - 1980. - lokakuu ( osa 27 , nro 4 ) . - s. 701-717 . - doi : 10.1145/322217.322225 .
Tutte, W.T. Lineaaristen graafien faktorointi (indefinite) // J. London Math. Soc.. - 1947. - huhtikuu ( osa 22 , nro 2 ). - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .
Zippel, Richard. Todennäköisyyspohjaiset algoritmit harvalle polynomille . - 1979. - Voi. 72. - s. 216-226. — ISBN 978-3-540-09519-4 . - doi : 10.1007/3-540-09519-5_73 .
Zippel, Richard Relativisoidun satunnaisen polynomiajan ja suhteellisen deterministisen polynomiajan eksplisiittinen erottelu (ps) (helmikuu 1989). Haettu: 15.6.2008. (määrätön)
Zippel, Richard. Tehokas polynomilaskenta (neopr.) / Springer. - 1993. - T. 241. - (The Springer International Series in Engineering and Computer Science). - ISBN 978-0-7923-9375-7 .

Linkit

Richard J. Liptonin Schwartz-Zippel Lemman omituinen historia