Associativitetstest

Associativitetstest - kontrollerar en binär operation för associativitet . Den naiva verifieringsproceduren, som består i uppräkning av alla möjliga tripletter av operationsargument, tar tid, där är storleken på den uppsättning över vilken operationen definieras. Tidiga associativitetstester gav inga asymptotiska förbättringar jämfört med den naiva algoritmen, men förbättrade körtiden i vissa speciella fall. Till exempel fann Robert Tarjan 1972 att Lights test, som föreslogs 1949, gör det möjligt att kontrollera om den binära operationen som studeras är reversibel (ger en kvasigrupp $O(n^{3})$ $n$ $O(n^{2}\log n)$ ). Det första probabilistiska testet som förbättrar körtiden från till föreslogs 1996 av Sridhar Rajagopalan och Leonard Shulman . 2015 föreslogs en kvantalgoritm som kontrollerar en operation för associativitet i tid , vilket är en förbättring jämfört med Grovers sökning , som körs i [1] . $O(n^{3})$ ${\textstil O(n^{2}\log \delta ^{-1})}$ ${\textstyle O(n^{10/7})}$ ${\textstyle O(n^{3/2})}$

Förklaring av problemet

Givet en storlekstabell som beskriver en sluten operation på en storleksuppsättning , det vill säga operationen ges av dess Cayley-tabell , och tillsammans med denna operation bildar en magma . Det är nödvändigt att kontrollera att den är uppfylld (med andra ord, operationen är associativ ). Varje deterministisk algoritm som löser detta problem kommer att kräva inte mindre tid, eftersom varje cell i Cayley-tabellen måste läsas minst en gång. Iterativ uppräkning av alla trippel , att kontrollera att likheten gäller för varje trippel, tar tid [2] . $n\ gånger n$ $\cdot :G\times 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

Att kontrollera associativitet är ett av de naturliga problem som uppstår när man arbetar med Cayley-tabeller för olika operationer [3] . I synnerhet implementeras en sådan kontroll i datoralgebrasystemen GAP [4] och Maple [5] . I det mest allmänna fallet finns det operationer för vilka alla utom en av trippelna är associativa - ett exempel på en sådan operation på element är operationen sådan att , och för alla andra element . Dess enda icke-associativa trippel är , eftersom [6] . På grund av förekomsten av sådana operationer kan man få intrycket att associativitetskontrollen kommer att kräva bearbetning av alla möjliga trippel och därför är en asymptotisk förbättring av algoritmens gångtid omöjlig [7] . Av samma anledning kommer en naiv probabilistisk algoritm som kontrollerar associativiteten hos slumpmässigt utvalda trippel att kräva kontroller för att garantera en tillräckligt låg felsannolikhet [8] . Algoritmen som Rajagopalan och Shulman föreslagit visar dock att denna uppskattning kan förbättras, och fungerar som ett tydligt exempel på hur probabilistiska algoritmer kan hantera problem som ser svåra ut för deterministiska algoritmer - från och med 2020 löser deterministiska algoritmer ett givet problem i subkubisk tid , okänd [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})$

Light's test

1961 publicerade Alfred Clifford och Gordon Preston i boken Algebraic Semigroup Theory ett associativitetstest som rapporterades till en av författarna av Dr. Light 1949. Algoritmen består i att överväga för varje operation och . Per definition är en operation associativ om och endast om (Cayleys operationstabeller är desamma) för alla [10] . Ljus märkte att om , det vill säga y har en generatoruppsättning , så är det tillräckligt att kontrollera endast för [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$

Om i definitionerna ovan och , då . $\star _{a}=\circ _{a}$ ${\displaystyle \star _{b}=\circ _{b))$ ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b))$

Bevis

Låt det vara för alla . Sedan . ■ $(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ärsta fall (till exempel för maximal drift ) kan den minsta magmageneratoruppsättningen bestå av element, så testet måste utföras för alla element , vilket kommer att ta tid. 1972 märkte Robert Tarjan att Lights test kan vara effektivt för att testa om en given operation definierar en grupp [2] . Detta beror på det faktum att för vissa speciella typer av operationer, inklusive operationer som uppfyller gruppaxiomet för närvaron av ett inverst element , är det alltid möjligt att välja en genererande uppsättning av liten storlek [12] . ${\textstyle n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Låt vilken som helst ekvation av formen ha en unik lösning (det vill säga en kvasigrupp ). Då är det möjligt att välja ut en genereringsuppsättning av storlek som mest . $G$ $a=b\cdot x$ $x$ $G$ $G$ $S$ $\lfloor \log _{2}n\rfloor +1$

Bevis

Låta vara någon delmängd sådan att och . Sedan, på grund av det faktum att det är en kvasigrupp, , eftersom alla element i formuläret för är olika och inte ingår i . Således kan sekventiell tillägg till elementen i vyn inte göras mer än en gång. ■ $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 är en kvasigrupp om och endast om dess Cayley-tablå är en latinsk kvadrat , som kan verifieras i tid . Tillämpningen av förfarandet som beskrivs ovan på en kvasigrupp tillåter i sin tur att deterministiskt kontrollera om , är en grupp , för [13] . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Rajagopalan-Schulman test

Det första subkubiska testet var Monte Carlo-algoritmen som föreslogs 1996 [14] Sridhar Rajagopalan från Princeton University och Leonard Shulman från Georgia Institute of Technology . Proceduren som föreslås av dem kräver tid, där är den maximalt tillåtna felsannolikheten [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritm

Algoritmen använder en groupoidalgebra — ett linjärt utrymme ( algebra ) över ett dimensionsfält med två element , vars basvektorer motsvarar alla de olika elementen i magman . Vektorerna för ett sådant utrymme 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 }}=\summa \limits _{g\in G}a_{g}v_{g}}

, var

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

De har summaoperationen

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

, där betecknar addition och in

\ plus

{\displaystyle a_{g))

{\displaystyle b_{g))

\mathbb {Z} _{2},

samt produktdriften

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

, där anger produkten och in

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

{\displaystyle a_{x))

{\displaystyle b_{y))

\mathbb {Z} _{2}.

Produkten av vektorer i en sådan algebra blir mer intuitiv om vi anser att för vilket par av basvektorer det definieras som , och produkten av alla andra vektorpar erhålls genom att "öppna parenteserna" och ordna om termerna. Till exempel, för produkten har formen ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$ $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}),

och substitution resulterar i ett uttryck som motsvarar den allmänna definitionen [8] . För algebra definierad på detta sätt gäller följande lemma [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

Den initiala magmaoperationen är associativ om och endast om för någon . Om operationen inte är associativ överstiger inte sannolikheten att den angivna likheten kommer att uppfyllas för en slumpmässigt enhetligt vald trippel . $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}}}$

För att kontrollera associativiteten väljs slumpmässiga sådana , för vilka . En sådan kontroll kan utföras i tid , och för att uppnå en felsannolikhet som inte överstiger , räcker det med kontroller, vilket ger den totala gångtiden [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))$ ${\textstil O\left(n^{2}\log \delta ^{-1}\right)}$

Godtyckliga operationer

Rajagopalans och Shulmans tillvägagångssätt kan generaliseras för att testa allmänna identiteter, förutsatt att varje variabel förekommer exakt en gång på vänster och höger sida av identiteten [16] .

Till exempel kan vi överväga en uppsättning på de element av vilka tre operationer är specificerade: "union" , "korsning" och "addition" . Det är nödvändigt att kontrollera det . För att göra detta kan vi överväga de inducerade på operationer $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]$

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

, och

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

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

och kontrollera att det är sant för dessa operationer . I den mest allmänna formen kan proceduren karakteriseras av följande teorem [16] : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Låta vara ändliga mängder, och vara en uppsättning operationer definierade på ändliga kartesiska produkter av dessa mängder så att operationen definieras på mängden , där är arity av operationen . Sedan kan verifieringen av sanningen av identiteten som består av dessa operationer, så att varje variabel förekommer i dess vänstra och högra delar exakt en gång, utföras i tiden , där är den största möjliga storleken på definitionsdomänen , är det totala antalet av operationer som används i identiteten, är det totala antalet variabler, är den största tillåtna felsannolikheten. ${\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})$ ${\textstil 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 fallet har operationen en storleksdomän , och därför tar procedurens beräkningskomplexitet formen , medan en naiv kontroll skulle kräva 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})$

Detta resultat kan förbättras om vi istället betraktar algebra som ett primtal . I detta fall kan enligt Schwarz-Zippel-lemmat sannolikheten för att motbevisa en felaktig identitet i en iteration förbättras från till , vilket motsvarar en konstant sannolikhet för och gör att vi kan förbättra körtiden till [6] . $\mathbb {Z} _{2}[G]$ $\mathbb {Z} _{p}[G]$ $p>k$ ${\textstil {\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ök efter ett icke-identitetsvittne

Algoritmen kan modifieras för att hitta en viss uppsättning variabler där identiteten misslyckas. Överväg till exempel att söka efter en icke-associativ trippel i tid . Låt det vara känt för vissa att . Dessa element kan associeras med en trippel , så att om , då är också lika med , och om , då väljs slumpmässigt mellan och (på liknande sätt för och ). För sannolikheten att , kommer uppskattningen underifrån fortfarande att vara sann , så proceduren kan upprepas tills vart och ett av elementen har en enhet i endast en av positionerna, vilket kommer att motsvara den önskade icke-associativa trippeln i [17] . ${\textstil (a,b,c)}$ ${\textstil 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$ $ett$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $A',B',C'$ $G$

Anteckningar

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , sid. 120
↑ 1 2 Lipton, Regan, 2013
↑ IsAssociative . _ GAP-Referensmanual . GAP-gruppen. Hämtad 1 september 2021. Arkiverad från originalet 17 april 2021.
↑ IsAssociative . _ Maple Hjälp . maplesoft. Hämtad 14 augusti 2022. Arkiverad från originalet 14 april 2021.
↑ 1 2 Rajagopalan, Schulman, 2000 , sid. 1162
↑ 12 Sinclair , 2020
↑ 1 2 Matousek, Nešetřil, 2008
↑ Schulman, 2020
↑ Premchand, 1984 , sid. 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

Litteratur

Clifford A., Preston G. Light's associativity test (engelska) // The Algebraic Theory of Semigroups - USA : AMS , 1961. - Vol. 1. - S. 7-8. — 224 sid. - ISBN 0-8218-0271-2 - doi:10.1090/SURV/007.1
Lee T., Magniez F., Santha M. Förbättrade Quantum Query Algorithms for Triangle Detection and Associativity Testing (engelska) // Algorithmica - Springer Science + Business Media , 2015. - Vol. 77, Iss. 2. - P. 459-486. — 1302 sid. — ISSN 0178-4617 ; 1432-0541 - doi:10.1007/S00453-015-0084-9 - arXiv:1210.1014
Lipton R. J. , Regan K. W. Leonard Schulman: Associativitet (engelska) // People, Problems, and Proofs : Essays from Gödels Lost Letter: 2010 - 2013. - P. 297-299. — 333 sid. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Probabilistisk associativitetstestning (engelska) // Invitation to Discrete Mathematics - 2 - NYC : OUP , 2008. - P. 388-392. — 443 sid. — ISBN 978-0-19-857043-1
Premchand S. Independence of axioms for biordered sets (engelska) // Semigroup Forum - Springer Science + Business Media , 1984. - Vol. 28, Iss. 1. - P. 249-263. — 397 sid. — ISSN 0037-1912 ; 1432-2137 - doi:10.1007/BF02572487
Rajagopalan S., Schulman L. J. Verifiering av identiteter // SIAM J. Comput . / M. Sudan - SIAM , 2000. - Vol. 29, Iss. 4. - P. 1155-1163. — 2097 sid. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verifiering av identiteter (engelska) // 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 (engelska) // Probability and Algorithms - California Institute of Technology , 2020. - S. 35-37. — 108p.
Sinclair A. Checking associativity (engelska) // Randomness & Computation - UC Berkeley , 2020. - P. 5-6. - 7 p.
Tarjan R. E. Avgöra om en groupoid är en grupp // Inform . bearbeta. Lett. - Elsevier BV , 1972. - Vol. 1, Iss. 3. - S. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9