Associativitetstest

Associativitetstest - kontrol af en binær operation for associativitet . Den naive verifikationsprocedure, som består i opregning af alle mulige tripletter af operationsargumenter, tager tid, hvor er størrelsen af det sæt, som operationen er defineret over. Tidlige associativitetstests gav ikke asymptotiske forbedringer i forhold til den naive algoritme, men forbedrede køretiden i nogle specielle tilfælde. For eksempel fandt Robert Tarjan i 1972, at Lights test, foreslået i 1949, gør det muligt at kontrollere, om den undersøgte binære operation er reversibel (giver en kvasigruppe $O(n^{3})$ $n$ $O(n^{2}\log n)$ ). Den første probabilistiske test, der forbedrer køretiden fra til , blev foreslået i 1996 af Sridhar Rajagopalan og Leonard Shulman . I 2015 blev der foreslået en kvantealgoritme , der kontrollerer en operation for associativitet i tide , hvilket er en forbedring i forhold til Grovers søgning , som kører i [1] . $O(n^{3})$ ${\tekststil O(n^{2}\log \delta ^{-1})}$ ${\textstyle O(n^{10/7})}$ ${\textstyle O(n^{3/2})}$

Udtalelse af problemet

Givet en tabel af størrelse , der beskriver en lukket operation på et sæt af størrelse , dvs. operationen er givet af dens Cayley-tabel , og sammen med denne operation danner en magma . Det er nødvendigt at kontrollere, at for enhver den er opfyldt (med andre ord, operationen er associativ ). Enhver deterministisk algoritme, der løser dette problem, kræver ikke mindre tid, da hver celle i Cayley-tabellen skal læses mindst én gang. Iterativ opregning af alle tripler , kontrol af, at lighed gælder for hver tripel, tager tid [2] . $n\ gange n$ $\cdot :G\ gange G\mapsto G$ $G$ $n$ $\cdot$ $G$ $a,b,c\in G$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ $O(n^{2})$ $a,b,c$ $O(n^{3})$

Motivation

Kontrol af associativitet er et af de naturlige problemer, der opstår, når man arbejder med Cayley-tabeller over forskellige operationer [3] . En sådan kontrol er især implementeret i GAP [4] og Maple [5] computeralgebrasystemerne . I det mest generelle tilfælde er der operationer, hvor alle på nær én af triplerne er associative - et eksempel på en sådan operation på elementer er operationen sådan, at , og for alle andre elementer . Dens eneste ikke-associative tripel er , fordi [6] . På grund af eksistensen af sådanne operationer kan man få det indtryk, at associativitetskontrollen vil kræve behandling af alle mulige tripler, og derfor er en asymptotisk forbedring af algoritmens køretid umulig [7] . Af samme grund vil en naiv probabilistisk algoritme, der kontrollerer associativiteten af tilfældigt udvalgte tripler, kræve kontroller for at garantere en tilstrækkelig lav fejlsandsynlighed [8] . Algoritmen foreslået af Rajagopalan og Shulman viser dog, at dette estimat kan forbedres, og fungerer som et tydeligt eksempel på, hvordan probabilistiske algoritmer kan klare problemer, der ser vanskelige ud for deterministiske algoritmer - fra 2020 løser deterministiske algoritmer et givet problem i subkubisk tid , ukendt [9] . $n\geq 3$ $\cdot$ $1\cdot 2=2$ $a\cdot b=3$ $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})$

Lysets test

I 1961 udgav Alfred Clifford og Gordon Preston i bogen Algebraic Semigroup Theory en associativitetstest rapporteret til en af forfatterne af Dr. Light i 1949. Algoritmen består i at overveje for hver operation og . Per definition er en operation associativ hvis og kun hvis (Cayley-tabellerne over operationer er de samme) for alle [10] . Lys bemærkede, at hvis , dvs. y har et generatorsæt , så er det tilstrækkeligt kun at kontrollere for [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$

Hvis i definitionerne ovenfor og , så . $\star _{a}=\circ _{a}$ ${\displaystyle \star _{b}=\circ _{b))$ ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b))$

Bevis

Lad det være for alle . Så . ■ $(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$

I værste fald (for eksempel for maksimal drift ) kan det mindste magmageneratorsæt bestå af elementer, så testen skal udføres for alle elementer , hvilket vil tage tid. I 1972 bemærkede Robert Tarjan , at Lights test kan være effektiv til at teste, om en given operation definerer en gruppe [2] . Dette skyldes det faktum, at for nogle specielle typer operationer, herunder operationer, der opfylder gruppeaksiomet for tilstedeværelsen af et omvendt element , er det altid muligt at vælge et genereringssæt af lille størrelse [12] . ${\tekststil n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Lad enhver ligning af formen have en unik løsning (det vil sige en kvasigruppe ). Så er det muligt at udskille et generatorsæt af størrelse højst . $G$ $a=b\cdot x$ $x$ $G$ $G$ $S$ $\lfloor \log _{2}n\rfloor +1$

Bevis

Lade være nogle delmængde sådan, at og . Så, på grund af det faktum, at der er en kvasigruppe, , da alle elementer i formen for er forskellige og ikke er indeholdt i . Således kan sekventiel tilføjelse til elementerne i visningen ikke foretages mere end én gang. ■ $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$

Per definition er en kvasigruppe, hvis og kun hvis dens Cayley-tableau er en latinsk firkant , som kan verificeres i tide . Anvendelsen af den ovenfor beskrevne procedure på en kvasigruppe giver til gengæld mulighed for deterministisk at kontrollere, om , er en gruppe , for [13] . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Rajagopalan-Schulman test

Den første subkubiske test var Monte Carlo-algoritmen foreslået i 1996 [14] Sridhar Rajagopalan fra Princeton University og Leonard Shulman fra Georgia Institute of Technology . Proceduren foreslået af dem kræver tid, hvor er den maksimalt tilladte fejlsandsynlighed [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritme

Algoritmen bruger en groupoid algebra — et lineært rum ( algebra ) over et to-element dimensionsfelt , hvis basisvektorer svarer til alle de forskellige elementer i magmaen . Vektorerne af et sådant rum har formen $\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}}+\dots +a_{g_{n}}v_{g_{n }}=\sum \limits _{g\in G}a_{g}v_{g}}

, hvor

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

De har sumoperationen

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

, hvor angiver tilføjelse og ind

\plus

{\displaystyle a_{g))

{\displaystyle b_{g))

\mathbb {Z} _{2},

samt produktdriften

{\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}}

, hvor angiver produktet og i

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

{\displaystyle a_{x))

{\displaystyle b_{y))

\mathbb {Z} _{2}.

Produktet af vektorer i en sådan algebra bliver mere intuitivt, hvis vi tænker på, at det for et hvilket som helst par af basisvektorer er defineret som , og produktet af ethvert andet par af vektorer opnås ved at "åbne parenteserne" og omarrangere vilkårene. For eksempel, for produktet har formen ${\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}),

og substitution resulterer i et udtryk svarende til den generelle definition [8] . For algebraen defineret på denne måde gælder følgende lemma [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

Den indledende magmaoperation er associativ, hvis og kun hvis for nogen . Hvis operationen ikke er associativ, så overstiger sandsynligheden for, at den angivne lighed vil være opfyldt for en tilfældig ensartet valgt tripel, ikke . $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ $A,B,C\in \mathbb {Z} _{2}[G]$ $a,b,c$ ${\textstyle {\frac {7}{8}}}$

For at kontrollere associativiteten vælges tilfældige , for hvilke . Et sådant tjek kan udføres i tide , og for at opnå en fejlsandsynlighed på højst , er det nok at lave tjek, som giver den samlede køretid [15] . $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)}$

Vilkårlige operationer

Rajagopalans og Shulmans tilgang kan generaliseres til at teste generelle identiteter, forudsat at hver variabel forekommer nøjagtigt én gang på venstre og højre side af identiteten [16] .

For eksempel kan vi overveje et sæt på de elementer, hvoraf tre operationer er specificeret: "union" , "skæringspunkt" og "addition" . Det er nødvendigt at kontrollere det . For at gøre dette, kan vi overveje induceret på operationer $G$ $a\cup b$ $a\cap b$ ${\bar {a}}$ ${\overline {a\cap (b\kop 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}

, og

{\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

og kontroller, at for disse operationer er det sandt . I den mest generelle form kan proceduren karakteriseres ved følgende teorem [16] : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\kop C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Lade være endelige mængder, og være et sæt af operationer defineret på endelige kartesiske produkter af disse sæt sådan, at operationen er defineret på sættet , hvor er arity af operationen . Derefter kan verificeringen af sandheden af identiteten sammensat af disse operationer, således at hver variabel forekommer i dens venstre og højre del nøjagtigt én gang, udføres i tid , hvor er den størst mulige størrelse af definitionsdomænet , er det samlede antal af operationer brugt i identiteten, er det samlede antal variabler, er den største tilladte fejlsandsynlighed. ${\displaystyle D_{1},\dots ,D_{k))$ ${\displaystyle \circ _{1},\dots ,\circ _{m))$ ${\displaystyle \circ _{j))$ ${\displaystyle D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j)))))$ ${\displaystyle c_{j))$ ${\displaystyle \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)}$ ${\displaystyle \circ _{j))$ $l$ $k$ $\delta$

I tilfælde af, at operationen har et størrelsesdomæne , og derfor tager den beregningsmæssige kompleksitet af proceduren formen , mens en naiv kontrol ville kræve operationer [16] . $|D_{1}|=\dots =|D_{k}|=n$ ${\displaystyle \circ _{j))$ $n^{c_{j))$ $M=n^{\max c_{j))$ $O(2^{k}ln^{\max c_{j))\log \delta ^{-1})$ $O(ln^{k})$

Dette resultat kan forbedres, hvis vi i stedet betragter algebraen som et primtal . I dette tilfælde, ifølge Schwarz-Zippel-lemmaet , kan sandsynligheden for at tilbagevise en forkert identitet i én iteration forbedres fra til , hvilket svarer til en konstant sandsynlighed for og giver os mulighed for at forbedre køretiden til [6] . $\mathbb {Z} _{2}[G]$ $\mathbb {Z} _{p}[G]$ $p>k$ ${\tekststil {\frac {1}{2^{k))))$ ${\textstyle 1-{\frac {k}{p}}}$ $p\sim (1+\varepsilon )k$ ${\textstyle {\frac {\varepsilon }{1+\varepsilon }}}$ $O(lM\log \delta ^{-1})$

Søg efter et ikke-identitetsvidne

Algoritmen kan modificeres til at finde et bestemt sæt af variabler, hvor identiteten fejler. Overvej f.eks. at søge efter en ikke-associativ trippel i tid . Lad det være kendt for nogle at . Disse elementer kan associeres med en tredobbelt , sådan at hvis , Så er også lig med , og hvis , så vælges tilfældigt mellem og (på samme måde for og ). For sandsynligheden for, at , vil estimatet nedefra stadig være sandt , så proceduren kan gentages, indtil hvert af elementerne kun har en enhed i en af positionerne, som vil svare til den ønskede ikke-associative tripel i [17] . ${\tekststil (a,b,c)}$ ${\textstyle O\left(n^{2}\log n\log \delta ^{-1}\right)}$ $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$ $en$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $A',B',C'$ $G$

Noter

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , s. 120
↑ 1 2 Lipton, Regan, 2013
↑ IsAssociative . _ GAP-referencemanual . GAP-gruppen. Hentet 1. september 2021. Arkiveret fra originalen 17. april 2021.
↑ IsAssociative . _ Maple Hjælp . maplesoft. Hentet 14. august 2022. Arkiveret fra originalen 14. april 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 , pp. 1158-1159
↑ Rajagopalan, Schulman, 2000 , s. 1159-1160

Litteratur

Clifford A., Preston G. Light's associativity test (engelsk) // The Algebraic Theory of Semigroups - USA : AMS , 1961. - Vol. 1. - S. 7-8. — 224 s. - ISBN 0-8218-0271-2 - doi:10.1090/SURV/007.1
Lee T., Magniez F., Santha M. Forbedrede kvanteforespørgselsalgoritmer til trekantsdetektion og associativitetstest (engelsk) // Algorithmica - Springer Science + Business Media , 2015. - Vol. 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: Associativitet (engelsk) // People, Problems, and Proofs : Essays from Gödels Lost Letter: 2010 - 2013. - S. 297-299. — 333 s. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Probabilistisk associativitetstest (engelsk) // Invitation to Discrete Mathematics - 2 - NYC : OUP , 2008. - S. 388-392. — 443 s. — ISBN 978-0-19-857043-1
Premchand S. Independence of axioms for biordered sets (engelsk) // Semigroup Forum - Springer Science + Business Media , 1984. - Vol. 28, Iss. 1. - S. 249-263. — 397 s. — ISSN 0037-1912 ; 1432-2137 - doi:10.1007/BF02572487
Rajagopalan S., Schulman L. J. Verifikation af identiteter // SIAM J. Comput . / M. Sudan - SIAM , 2000. - Vol. 29, Iss. 4. - S. 1155-1163. — 2097 s. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verifying identities (engelsk) // 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. Verifying Associativity (engelsk) // Probability and Algorithms - California Institute of Technology , 2020. - S. 35-37. — 108 sider.
Sinclair A. Checking associativity (engelsk) // Randomness & Computation - UC Berkeley , 2020. - S. 5-6. - 7 p.
Tarjan R. E. Bestemmelse af, om en groupoid er en gruppe // Inform . behandle. Lett. - Elsevier BV , 1972. - Vol. 1, Iss. 3. - S. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9