Schwarz-Zippel Lemma

A Schwartz-Zippel- lemma (a DeMillo -Lipton-Schwartz-Sippel-lemma is) egy olyan eredmény, amelyet széles körben használnak a polinomok egyenlőségének ellenőrzésére , vagyis arra a problémára, hogy sok változóból álló polinomokat ellenőrizzünk a nullával azonos egyenlőség szempontjából. A lemmát egymástól függetlenül Jack Schwartz [1] , Richard Zippel [2] , valamint Richard DeMillo és Richard Lipton fedezte fel , bár DeMillo és Lipton változata egy évvel megelőzi Schwartz és Zippel eredményét [3] . A véges mezőkre vonatkozó lemma egy változatát Oistin Ore bizonyította 1922-ben [4] .

Lemma

A feladat bemenete a mező feletti változók polinomja . Megadható számtani séma formájában vagy valamilyen polinommátrix determinánsaként . Jelenleg nem ismert olyan determinisztikus szubexponenciális algoritmus, amely lehetővé tenné annak ellenőrzését, hogy ez a polinom nem nulla. Vannak azonban ismert randomizált algoritmusok, amelyek ezt a problémát polinomiális időben oldják meg. Ezek elemzésekor általában meg kell becsülni annak valószínűségét, hogy egy nem nulla polinom egy véletlenszerűen kiválasztott pontban nullával lesz egyenlő. A Schwartz-Zippel-lemma a következőképpen van megfogalmazva: $n$ $\mathbb {F}$

Legyen egy nem nulla fokos polinom a mező felett . Legyen véges részhalmaz , és válasszuk ki az elemeket egységesen és egymástól függetlenül. Akkor . $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 }}$

Bizonyíték

Egy változó esetén a lemma egyenesen következik abból, hogy egy fokszámú polinomnak legfeljebb különböző gyöke lehet a mező felett . $d$ $d$ $\mathbb {F}$

A lemma általános formában igazolható a változók számának matematikai indukciójával . Az alapesetet fentebb bizonyítottuk. $n$ $n=1$

Legyen most igaz a tétel a változókon lévő összes polinomra. -ben polinomnak tekinthető , alakba írva $n-1$ $P$ $x_{1}$

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

Mivel nem egyenlő nullával, van néhány olyan szám , amely szintén nem egyenlő nullával. Legyen az ilyen számok közül a legnagyobb. Majd mivel a mértéke nem haladja meg . $P$ $én$ $P_{i}$ $én$ $\deg P_{i}\leq di$ ${\displaystyle x_{1}^{i}P_{i))$ $d$

Legyen most véletlenszerűen kiválasztva . Az indukciós hipotézis szerint . ${\displaystyle r_{2},\dots ,r_{n))$ $S$ $\Pr[P_{i}(r_{2},\ldots ,r_{n})=0]\leq {\frac {di}{|S|}}$

Ha , akkor foka van (és ezért nem egyenlő nullával), ezért $P_{i}(r_{2},\ldots ,r_{n})\neq 0$ $P(x_{1},r_{2},\ldots ,r_{n})$ $én$

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

Ha egy eseményt , eseményt néven és egy eseményen kívül ként jelölünk meg , akkor $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{igazított}}

■

Alkalmazások

A Schwarz-Sippel lemma jelentősége és a polinomok egyenlőségének igazolása az erre a problémára redukálható algoritmusokból következik.

Két polinom összehasonlítása

Adott két polinom és , igaz-e, hogy $p_{1}(x)$ $p_{2}(x)$

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

Ez a probléma a polinomok egyenlőségének ellenőrzésére redukálható, mivel ezt elegendő ellenőrizni

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

Így ha meg lehet határozni azt

p(x)\equiv 0,

ahol

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

akkor azt is meg lehet határozni, hogy az adott két polinom egyenlő-e.

Két polinom összehasonlítása felhasználható elágazó programok elemzésénél . Az egyszer olvasható elágazó program többlineáris polinomként ábrázolható, amely (bizonyos mezőn keresztül) nullákból és egyesekből ugyanazt a logikai függvényt értékeli, mint az elágazó program. Így két elágazó program akkor és csak akkor értékeli ki ugyanazt a Boole-függvényt, ha a megfelelő polinomok egyenlőek. Ez azt jelenti, hogy az elágazással rendelkező, egyszer olvasható programok által kiszámított Boole-függvények egyenlőségének ellenőrzése a polinomok egyenlőségének ellenőrzésére redukálható.

Egyszerűség teszt

Ha adott egy szám , az prímszám ? $n\in \mathbb {Z^{+}}$ $n$

Manindra Agrawal és Somenath Biswas egy egyszerű randomizált algoritmust dolgozott ki polinomiális egyenlőség tesztek segítségével annak meghatározására, hogy egy szám prím-e . $n$

Megmutatták, hogy minden prímszám (és csak a prímszámok) megfelel a következő összehasonlításnak: $n$

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

Ez az eredmény a Frobenius-endomorfizmusból következik .

Hadd

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

Akkor és csak akkor, ha prímszám [5] . Mivel azonban lehet prímszám, de lehet, hogy nem, a Schwartz-Zippel módszer itt nem működik. Az Agrawal és a Biswa kifinomultabb technikát használ, amely magában foglalja a kis fokú véletlenszerű redukált polinommal való osztást. ${\mathcal {P}}_{n}(z)=0\;({\mbox{mod}}\;n)$ $n$ $n$ ${\mathcal {P}}_{n}$

Tökéletes illeszkedés

Adott egy gráf csúcsokon , $G=(V,E)$ ahol páros szám. Tökéletes illeszkedést tartalmaz ? $n$ $n$ $G$

A Tutt-mátrix determinánsa akkor és csak akkor nem azonos nulla polinom , ha a gráf tökéletes illeszkedést tartalmaz.

( Tutte 1947 )

Egy élhalmaz egy részhalmazát illesztésnek nevezzük, ha minden csúcs -ból incidens legfeljebb egy éllel -ból . Az illesztést tökéletesnek nevezzük, ha minden csúcspontja pontosan az egyik élével esik . A Tatta mátrix egy mátrix: $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}}

ahol

a_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ és }}i<j\ \-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ és }}i>j\\0\;\;\;\;{\ mbox{egyébként}}.\end{cases}}

A Tutt-mátrix determinánsa (polinomként -ben ) ennek a ferde-szimmetrikus mátrixnak a determinánsaként van megadva , amely egyenlő a mátrix Pfaffiánjának négyzetével, és akkor és csak akkor nem nulla, ha tökéletes egyezés van a grafikont. $x_{ij},i<j$ $A$

Így a polinomiális egyenlőség teszt segítségével ellenőrizhető, hogy egy tetszőleges gráf tartalmaz-e tökéletes illeszkedést. $G$

A csúcsokban lévő kiegyensúlyozott bipartit gráf speciális esetben a Tatta mátrix blokkmátrix formát ölt. ${\megjelenítési stílus n=m+m}$

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

Az első sorokat (és ennek megfelelően az oszlopokat) a kétrészes gráf első része, az utolsó sorokat pedig a második rész indexeli. Ebben az esetben a Pfaffian (egy előjelig) egybeesik a méretmátrix szokásos determinánsával . A mátrix ekkor az adott bipartit gráf Edmonds-mátrixa . $m$ $m$ $x$ $m \szer m$ $x$

Jegyzetek

↑ ( Schwartz 1980 )
↑ ( Zippel 1979 )
↑ ( DeMillo és Lipton 1978 )
↑ Ö. Ore, Über höhere Kongruenzen. nork mat. Forenings Skrifter Ser. I (1922), sz. 7, 15 oldal.
↑ ( Agrawal 2003 )

Irodalom

Agrawal, Manindra; Biswas, Somenath. Elsődlegesség és identitás tesztelése kínai maradékon keresztül // Journal of the ACM : Journal. - 2003. - 1. évf. 50 , sz. 4 . - P. 429-443 . - doi : 10.1145/792538.792540 .
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech Az erősen tömörített kétdimenziós szövegek mintaillesztésének összetettségéről // Journal of Computer and System Sciences : folyóirat. - 2002. - 20. évf. 65 , sz. 2 . - P. 332-350 . - doi : 10.1006/jcss.2002.1852 .
Grigorjev, Dima; Karpinski, Marek. A polinomiálisan korlátos állandókkal rendelkező kétrészes gráfok illesztési problémája NC-ben van . - 1987. - P. 166-172. - ISBN 978-0-8186-0807-0 . - doi : 10.1109/SFCS.1987.56 .
Moshkovitz, Dana (2010). A Schwartz-Zippel-lemma alternatív bizonyítéka.
DeMillo, Richard A.; Lipton, Richard J.Valószínűségi megjegyzés az algebrai programok teszteléséhez // Information Processing Letters : folyóirat. - 1978. - 1. évf. 7 . - P. 193-195 . - doi : 10.1016/0020-0190(78)90067-4 .
Rudich, Steven. Számítási komplexitáselmélet (neopr.) / AMS. - 2004. - V. 10. - (IAS / Park City Mathematics Series). - ISBN 978-0-8218-2872-4 .
Schwartz, Jack Gyors valószínűségi algoritmusok polinomiális azonosságok ellenőrzésére (angol) // Journal of the ACM : Journal. - 1980. - október ( 27. évf. , 4. sz.). - P. 701-717 . - doi : 10.1145/322217.322225 .
Tutte, W.T. Lineáris gráfok faktorizálása (határozatlan) // J. London Math. Szoc.. - 1947. - április ( 22. évf. , 2. sz.). - S. 107-111 . - doi : 10.1112/jlms/s1-22.2.107 .
Zippel, Richard. Valószínűségi algoritmusok ritka polinomokhoz . - 1979. - 1. évf. 72. - P. 216-226. — ISBN 978-3-540-09519-4 . - doi : 10.1007/3-540-09519-5_73 .
Zippel, Richard A relativizált véletlenszerű polinomidő és a relativizált determinisztikus polinomidő (ps) explicit szétválasztása (1989. február). Letöltve: 2008. június 15. (határozatlan)
Zippel, Richard. Hatékony polinomszámítás (neopr.) / Springer. - 1993. - T. 241. - (The Springer International Series in Engineering and Computer Science). - ISBN 978-0-7923-9375-7 .

Linkek

A Schwartz-Zippel Lemma különös története , Richard J. Lipton