Assosiaatiotesti

Assosiaatiotesti - binäärioperaation assosiatiivisuuden tarkistaminen . Naivi varmennusmenettely, joka koostuu kaikkien mahdollisten operaatioargumenttien kolmosten luettelemisesta , vie aikaa, missä on sen joukon koko, jonka yli operaatio määritellään. Varhaiset assosiaatiotestit eivät tuottaneet asymptoottisia parannuksia naiiviin algoritmeihin verrattuna, mutta ne paransivat suoritusaikaa joissakin erikoistapauksissa. Esimerkiksi Robert Tarjan havaitsi vuonna 1972, että Lightin testi, jota ehdotettiin vuonna 1949, mahdollistaa sen tarkistamisen, onko tutkittava binäärioperaatio palautuva (määrittää kvasiryhmän ). Sridhar Rajagopalan ja Leonard Shulman ehdottivat vuonna 1996 ensimmäistä todennäköisyystestiä, joka parantaa ajoaikaa . Vuonna 2015 ehdotettiin kvanttialgoritmia , joka tarkistaa toiminnon assosiatiivisuuden ajassa , mikä on parannus Groverin hakuun , joka suoritetaan vuonna [1] . $O(n^{3})$ $n$ $O(n^{2}\log n)$ $O(n^{3})$ ${\textstyle O(n^{2}\log \delta ^{-1})}$ ${\textstyle O(n^{10/7})}$ ${\textstyle O(n^{3/2})}$

Ongelman selvitys

Annettu kokotaulukko , joka kuvaa suljettua operaatiota kokojoukolle , eli operaatio on annettu sen Cayley-taulukosta ja muodostaa yhdessä tämän operaation kanssa magman . On tarpeen tarkistaa, että se täyttyy mille tahansa (toisin sanoen operaatio on assosiatiivinen ). Mikä tahansa deterministinen algoritmi, joka ratkaisee tämän ongelman, ei vaadi vähemmän aikaa, koska jokainen Cayley-taulukon solu on luettava vähintään kerran. Kaikkien kolmioiden iteratiivinen laskeminen , joka tarkistaa, että tasa-arvo pätee jokaiselle kolmiolle, vie aikaa [2] . $n\ kertaa n$ $\cdot :G\times G\mapsto G$ $G$ $n$ $\cdot$ $G$ ${\näyttötyyli a,b,c\in G}$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ $O(n^{2})$ $a,b,c$ $O(n^{3})$

Motivaatio

Assosiatiivisuuden tarkistaminen on yksi luonnollisista ongelmista, joita syntyy käytettäessä eri operaatioiden Cayley-taulukoita [3] . Erityisesti tällainen tarkistus on toteutettu GAP [4] ja Maple [5] tietokonealgebrajärjestelmissä . Yleisimmissä tapauksissa on operaatioita, joissa kaikki kolmiot yhtä lukuun ottamatta ovat assosiatiivisia - esimerkki tällaisesta elementtien operaatiosta on operaatio sellainen, että , ja kaikille muille elementeille . Sen ainoa ei-assosiatiivinen kolmoisosa on , koska [6] . Tällaisten operaatioiden olemassaolon vuoksi voi saada vaikutelman, että assosiatiivisuustarkistus vaatii kaikkien mahdollisten kolmoiskappaleiden prosessointia ja siksi algoritmin ajoajan asymptoottinen parantaminen on mahdotonta [7] . Samasta syystä naiivi todennäköisyysalgoritmi, joka tarkistaa satunnaisesti valittujen kolmioiden assosiatiivisuuden, vaatii tarkistuksia riittävän alhaisen virhetodennäköisyyden takaamiseksi [8] . Rajagopalanin ja Shulmanin ehdottama algoritmi kuitenkin osoittaa, että tätä arviota voidaan parantaa, ja se toimii selkeänä esimerkkinä siitä, kuinka todennäköisyyspohjaiset algoritmit voivat selviytyä ongelmista, jotka näyttävät vaikeilta deterministisille algoritmeille - vuodesta 2020 lähtien deterministiset algoritmit ratkaisevat tietyn ongelman alikutiossa. aika , tuntematon [9] . $n\geq 3$ $\cdot$ $1\cdot 2=2$ $a\cdot b=3$ ${\näyttötyyli 1,1,2}$ $1\cdot (1\cdot 2)=1\cdot 2=2\neq 3=3\cdot 2=(1\cdot 1)\cdot 2$ $O(n^{3})$

Valon testi

Vuonna 1961 Alfred Clifford ja Gordon Preston julkaisivat kirjassa Algebraic Semigroup Theory assosiaatiotestin, jonka tohtori Light raportoi yhdelle kirjoittajista vuonna 1949. Algoritmi koostuu kunkin toiminnon ja . Määritelmän mukaan operaatio on assosiatiivinen silloin ja vain jos (Cayley-operaatiotaulukot ovat samat) kaikille [10] . Light huomasi, että jos y :llä on generaattorijoukko , niin riittää, että tarkistat vain [11] [12] . $g\in G$ $x\star _{g}y=x\cdot (g\cdot y)$ $x\circ _{g}y=(x\cdot g)\cdot y$ $\cdot$ $\star _{g}=\circ _{g}$ $g\in G$ $G=\langle S\rangle$ $G$ $S$ $g\in S$

Jos yllä olevissa määritelmissä ja , niin . $\star _{a}=\circ _{a}$ ${\displaystyle \star _{b}=\circ _{b))$ ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b))$

Todiste

Olkoon se kaikille . Sitten . ■ $(x\cdot a)\cdot y=x\cdot (a\cdot y)$ $(x\cdot b)\cdot y=x\cdot (b\cdot y)$ $x,y\in G$ $x\cdot ((a\cdot b)\cdot y)=x\cdot (a\cdot (b\cdot y))=(x\cdot a)\cdot (b\cdot y)=(( x\cdot a)\cdot b)\cdot y=(x\cdot (a\cdot b))\cdot y$

Pahimmassa tapauksessa (esimerkiksi maksimitoimintaa varten ) pienin magmageneraattorisarja voi koostua elementeistä, joten testi on suoritettava kaikille elementeille , mikä vie aikaa. Vuonna 1972 Robert Tarjan huomasi, että Lightin testi voi olla tehokas testattaessa, määrittääkö tietty operaatio ryhmän [2] . Tämä johtuu siitä, että joillekin erikoistyyppisille operaatioille, mukaan lukien operaatiot, jotka täyttävät käänteisen elementin olemassaolon ryhmäaksiooman , on aina mahdollista valita pienikokoinen generointijoukko [12] . ${\textstyle n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Olkoon millä tahansa muodon yhtälöllä ainutlaatuinen ratkaisu ( eli kvasiryhmä ). Silloin on mahdollista erottaa korkeintaan koon generoiva joukko . $G$ $a=b\cdot x$ $x$ $G$ $G$ $S$ $\lfloor \log _{2}n\rfloor +1$

Todiste

Antaa olla osajoukko sellainen, että ja . Sitten, koska se on kvasiryhmä, , koska kaikki lomakkeen elementit ovat erilaisia eivätkä sisälly . Näin ollen peräkkäistä lisäystä näkymän elementteihin voidaan tehdä vain kerran. ■ $T\subset G$ $G$ $G\neq \langle T\rangle$ $b\in G\setminus \langle T\rangle$ $(G,\cdot )$ $\vert \langle T\cup \{b\}\rangle \vert \geq 2\vert \langle T\rangle \vert$ $t\cdot b$ $t\in \langle T\rangle$ $\langle T\rangle$ $T\neq \varnothing$ $b\in G\setminus \langle T\rangle$ $\log _{2}\vert G\vert$

Määritelmän mukaan se on kvasiryhmä, jos ja vain jos sen Cayley-taulukko on latinalainen neliö , joka voidaan varmistaa ajoissa . Edellä kuvatun proseduurin soveltaminen kvasiryhmään mahdollistaa puolestaan deterministisen tarkistamisen, onko , ryhmä , [13] . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Rajagopalan-Schulman testi

Ensimmäinen subkubinen testi oli Monte Carlo -tyyppinen algoritmi , ehdottivat vuonna 1996 Sridhar Rajagopalan Princetonin yliopistosta ja Leonard Shulman Georgia Institute of Technologysta . Niiden ehdottama menettely vaatii aikaa, missä on suurin sallittu virhetodennäköisyys [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritmi

Algoritmi käyttää ryhmäoidialgebraa — lineaarista avaruutta ( algebraa ) kaksielementtisen ulottuvuuskentän päällä , jonka kantavektorit vastaavat kaikkia magman eri elementtejä . Tällaisen avaruuden vektoreilla on muoto $\mathbb {Z} _{2}[G]$ $\mathbb{Z } _{2}$ $n$ $v_{g_{1}},\dots ,v_{g_{n}}$ $g_{1},\dots ,g_{n}$

{\textstyle A=a_{g_{1}}v_{g_{1}}+a_{g_{2}}v_{g_{2}}+\pisteet +a_{g_{n}}v_{g_{n }}=\summa \limits _{g\in G}a_{g}v_{g}}

, missä

a_{g}\in \mathbb {Z} _{2}.

Heillä on summaoperaatio

{\textstyle A+B=\sum \limits _{g\in G}(a_{g}\oplus b_{g})v_{g))

, jossa tarkoittaa lisäystä ja sisään

\oplus

{\displaystyle a_{g))

{\displaystyle b_{g))

\mathbb {Z} _{2},

sekä tuotteen toiminta

{\textstyle A\cdot B=\sum \limits _{x,y\in G}a_{x}b_{y}v_{x\cdot y}=\sum \limits _{g\in G}(\ bigoplus \limits _{x\cdot y=g}a_{x}b_{y})v_{g}}

, jossa tarkoittaa tuotetta ja sisään

{\displaystyle a_{x}b_{y))

{\displaystyle a_{x))

{\displaystyle b_{y))

\mathbb {Z} _{2}.

Tällaisen algebran vektorien tulosta tulee intuitiivisempi, jos otamme huomioon, että mille tahansa kantavektoriparille se määritellään muodossa , ja minkä tahansa muun vektoriparin tulo saadaan "avaamalla sulut" ja järjestämällä termit uudelleen. Esimerkiksi tuotteella on muoto ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$ ${\displaystyle G=\{p,q,r\))$

A\cdot B=(a_{p}v_{p}+a_{q}v_{q}+a_{r}v_{r})\cdot (b_{p}v_{p}+b_{ q}v_{q}+b_{r}v_{r})=a_{p}b_{p}(v_{p}\cdot v_{p})+a_{p}b_{q}(v_{p }\cdot v_{q})+\dots +a_{r}b_{r}(v_{r}\cdot v_{r}),

ja substituutio johtaa yleistä määritelmää vastaavaan lausekkeeseen [8] . Tällä tavalla määritellylle algebralle pätee seuraava lemma [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

Alkuperäinen magmaoperaatio on assosiatiivinen jos ja vain jos jollekin . Jos operaatio ei ole assosiatiivinen, todennäköisyys, että määritetty yhtäläisyys täyttyy satunnaisesti tasaisesti valitulle kolmikolle , ei ylitä . $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ ${\näyttötyyli A,B,C\in \mathbb {Z} _{2}[G]}$ $a,b,c$ ${\textstyle {\frac {7}{8}}}$

Assosiatiivisuuden tarkistamiseksi valitaan satunnaiset , joille . Tällainen tarkistus voidaan suorittaa ajoissa , ja virhetodennäköisyyden saavuttamiseksi, joka ei ylitä , riittää tarkastukset, jolloin saadaan kokonaisajoaika [15] . ${\näyttötyyli A,B,C\in \mathbb {Z} _{2}[G]}$ $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ $O(n^{2})$ $\delta$ ${\displaystyle \log _{8/7}\delta ^{-1))$ ${\textstyle O\left(n^{2}\log \delta ^{-1}\right)}$

Arbitrary Operations

Rajagopalanin ja Shulmanin lähestymistapaa voidaan yleistää testaamaan yleisiä identiteettejä edellyttäen, että jokainen muuttuja esiintyy täsmälleen kerran identiteetin vasemmalla ja oikealla puolella [16] .

Voimme esimerkiksi harkita joukkoa , jonka elementeille on määritetty kolme operaatiota: "liitto" , "risteys" ja "lisäys" . Se on tarpeen tarkistaa . Tätä varten voimme harkita indusoituja operaatioita $G$ $a\cup b$ $a\cap b$ ${\bar {a}}$ ${\overline {a\cap (b\cup c)))={\overline {a))\cup ({\overline {b))\cap {\overline {c)))$ $\mathbb {Z} _{2}[G]$

{\textstyle A\cup B=\sum \limits _{g\in G}\left(\bigoplus \limits _{x\cup y=g}a_{x}b_{y}\right)g}

, ja

{\textstyle A\cap B=\sum \limits _{g\in G}\left(\bigoplus \limits _{x\cap y=g}a_{x}b_{y}\right)g}

{\bar {A}}=\sum \limits _{g\in G}{\bar {a}}_{g}g

ja tarkista, että nämä toiminnot pitävät paikkansa . Yleisimmässä muodossa menettelyä voidaan luonnehtia seuraavalla lauseella [16] : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Antaa olla äärellisiä joukkoja, ja olla joukko operaatioita, jotka on määritelty näiden joukkojen äärellisille karteesisille tuloille siten, että operaatio on määritelty joukossa , jossa on operaation ariteetti . Tällöin näistä operaatioista koostuvan identiteetin totuuden varmistus siten, että jokainen muuttuja esiintyy vasemmassa ja oikealla osassa täsmälleen kerran, voidaan suorittaa ajassa , missä on määritelmäalueen suurin mahdollinen koko on kokonaisluku identiteetissä käytetyistä operaatioista, on muuttujien kokonaismäärä, on suurin sallittu virhetodennäköisyys. ${\displaystyle D_{1},\dots ,D_{k))$ ${\displaystyle \circ _{1},\dots ,\circ _{m))$ ${\näyttötyyli \circ _{j))$ ${\displaystyle D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j)))))$ ${\displaystyle c_{j))$ ${\näyttötyyli \circ _{j))$ $O(2^{k}lM\log \delta ^{-1})$ ${\textstyle M=\max _{j}\left(\vert D_{\sigma (j,1)}\vert \cdot \ldots \cdot \vert D_{\sigma (j,c_{j})}\ vert\right)}$ ${\näyttötyyli \circ _{j))$ $l$ $k$ $\delta$

Tapauksessa , operaatiolla on kokoalue ja siksi toimenpiteen laskennallinen monimutkaisuus saa muodon , kun taas naiivi tarkistus vaatisi operaatioita [16] . $|D_{1}|=\dots =|D_{k}|=n$ ${\näyttötyyli \circ _{j))$ ${\näyttötyyli n^{c_{j))}$ $M=n^{\max c_{j))$ $O(2^{k}ln^{\max c_{j))\log \delta ^{-1})$ $O(ln^{k})$

Tätä tulosta voidaan parantaa, jos sen sijaan tarkastellaan alkuluvun algebraa . Tässä tapauksessa Schwarz-Zippel-lemman mukaan todennäköisyyttä virheellisen identiteetin kumoamiseen yhdessä iteraatiossa voidaan parantaa arvosta arvoon , mikä vastaa jatkuvaa todennäköisyyttä ja mahdollistaa ajoajan parantamisen arvoon [6] . $\mathbb {Z} _{2}[G]$ $\mathbb {Z} _{p}[G]$ $p>k$ ${\textstyle {\frac {1}{2^{k))))$ ${\textstyle 1-{\frac {k}{p}}}$ $p\sim (1+\varepsilon )k$ ${\textstyle {\frac {\varepsilon }{1+\varepsilon }}}$ $O(lM\log \delta ^{-1})$

Etsi ei-identiteettiä todistaja

Algoritmia voidaan muokata etsimään tietty joukko muuttujia, joissa identiteetti epäonnistuu. Harkitse esimerkiksi ei-assosiatiivisen triplin etsimistä ajassa . Olkoon se joidenkin tiedossa . Nämä elementit voidaan liittää kolmioon siten, että jos , niin on myös yhtä suuri kuin , ja jos , niin valitaan satunnaisesti väliltä ja (samalla tavalla ja ). Todennäköisyydellä, että , alta tuleva estimaatti on edelleen tosi , joten menettelyä voidaan toistaa, kunnes jokaisella elementillä on yksikkö vain yhdessä paikassa, joka vastaa haluttua ei-assosiatiivista kolmoisosaa kohdassa [17] . ${\tekstyyli (a,b,c)}$ ${\textstyle O\left(n^{2}\log n\log \delta ^{-1}\right)}$ ${\näyttötyyli A,B,C\in \mathbb {Z} _{2}[G]}$ $A\cdot (B\cdot C)\neq (A\cdot B)\cdot C$ $A',B',C'$ $a_{i}=0$ $a_{i}'$ $0$ $a_{i}=1$ $a_{i}'$ $0$ $yksi$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $A',B',C'$ $G$

Muistiinpanot

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , s. 120
↑ 1 2 Lipton, Regan, 2013
↑ Isassosiatiivinen . _ GAP-viiteopas . GAP-ryhmä. Haettu 1. syyskuuta 2021. Arkistoitu alkuperäisestä 17. huhtikuuta 2021.
↑ Isassosiatiivinen . _ Maple Apua . vaahterasofta. Haettu 14. elokuuta 2022. Arkistoitu alkuperäisestä 14. huhtikuuta 2021.
↑ 1 2 Rajagopalan, Schulman, 2000 , s. 1162
↑ 12 Sinclair , 2020
↑ 1 2 Matousek, Nešetřil, 2008
↑ Schulman, 2020
↑ Premchand, 1984 , s. 257
↑ Clifford, Preston, 1961 , s. 7-8
↑ 1 2 Rajagopalan, Schulman, 2000 , s. 1155-1156
↑ Rajagopalan, Schulman, 2000 , s. 1160-1161
↑ Rajagopalan, Schulman, 1996
↑ 1 2 Rajagopalan, Schulman, 2000 , s. 1156-1157
↑ 1 2 3 Rajagopalan, Schulman, 2000 , s. 1158-1159
↑ Rajagopalan, Schulman, 2000 , s. 1159-1160

Kirjallisuus

Clifford A., Preston G. Lightin assosiaatiotesti (englanniksi) // The Algebraic Theory of Semigroups - USA : AMS , 1961. - Voi. 1. - s. 7-8. — 224 s. - ISBN 0-8218-0271-2 - doi:10.1090/SURV/007.1
Lee T., Magniez F., Santha M. Parannetut kvanttikyselyalgoritmit kolmion havaitsemiseen ja assosiaatiotestaukseen (englanniksi) // Algorithmica - Springer Science + Business Media , 2015. - Voi. 77, Iss. 2. - s. 459-486. — 1302 s. — ISSN 0178-4617 ; 1432-0541 - doi:10.1007/S00453-015-0084-9 - arXiv:1210.1014
Lipton R. J. , Regan K. W. Leonard Schulman: Assosiaatio (englanniksi) // Ihmiset, ongelmat ja todisteet : Esseitä Gödelin kadonneesta kirjeestä: 2010 - 2013. - S. 297-299. — 333 s. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Probabilistinen assosiatiivisuustestaus (englanniksi) // Kutsu diskreettiin matematiikkaan - 2 - NYC : OUP , 2008. - P. 388-392. — 443 s. — ISBN 978-0-19-857043-1
Premchand S. Aksioomien riippumattomuus biojärjestetyille joukoille (englanniksi) // Semigroup Forum - Springer Science + Business Media , 1984. - Voi. 28, Iss. 1. - s. 249-263. — 397 s. — ISSN 0037-1912 ; 1432-2137 - doi:10.1007/BF02572487
Rajagopalan S., Schulman L. J. Identiteettien tarkistaminen // SIAM J. Comput . / M. Sudan - SIAM , 2000. - Voi. 29, Iss. 4. - P. 1155-1163. — 2097 s. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verifying Identities (englanniksi) // Proceedings of 37th Conference on Foundations of Computer Science - 1996. - 638 s. - ISBN 0-8186-7594-2 - ISSN 0272-5428 - doi:10.1109/SFCS.1996.548520
Schulman L. Assosiatiivisuuden varmistaminen (englanniksi) // Probability and Algorithms - California Institute of Technology , 2020. - S. 35-37. - 108 p.
Sinclair A. Assosiatiivisuuden tarkistaminen (englanti) // Randomness & Computation - UC Berkeley , 2020. - S. 5-6. - 7p.
Tarjan R. E. Sen määrittäminen, onko ryhmäoidi ryhmä // Inform . prosessi. Lett. - Elsevier BV , 1972. - Voi. 1, Iss. 3. - s. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9