Test de asociativitate

Test de asociativitate - verificarea unei operații binare pentru asociativitate . Procedura de verificare naivă, care constă în enumerarea tuturor tripletelor posibile ale argumentelor operației, durează , unde este dimensiunea mulțimii peste care este definită operația. Testele de asociativitate timpurii nu au oferit îmbunătățiri asimptotice față de algoritmul naiv, dar au îmbunătățit timpul de rulare în unele cazuri speciale. De exemplu, Robert Tarjan a descoperit în 1972 că testul lui Light, propus în 1949, permite testarea dacă operația binară studiată este reversibilă (specifică cvasigrupul $O(n^{3})$ $n$ $O(n^{2}\log n)$ ). Primul test probabilistic care îmbunătățește timpul de rulare de la până la a fost propus în 1996 de Sridhar Rajagopalan și Leonard Shulman . În 2015, a fost propus un algoritm cuantic care verifică o operație pentru asociativitate în timp , ceea ce reprezintă o îmbunătățire față de căutarea lui Grover , care rulează în [1] . $O(n^{3})$ ${\textstyle O(n^{2}\log \delta ^{-1})}$ ${\textstyle O(n^{10/7})}$ ${\textstyle O(n^{3/2})}$

Enunțul problemei

Având în vedere un tabel de mărime care descrie o operație închisă pe un set de dimensiuni , adică operația este dată de tabelul său Cayley și împreună cu această operație formează o magmă . Este necesar să se verifice dacă pentru oricare este satisfăcut (cu alte cuvinte, operația este asociativă ). Orice algoritm determinist care rezolvă această problemă va necesita nu mai puțin timp, deoarece fiecare celulă a tabelului Cayley trebuie citită cel puțin o dată. Enumerarea iterativă a tuturor triplelor , verificând dacă egalitatea este valabilă pentru fiecare triplă, durează [ 2] . $n\ ori n$ $\cdot:G\time G\mapsto G$ $G$ $n$ $\cdot$ $G$ $a,b,c\în G$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ $O(n^{2})$ $a,b,c$ $O(n^{3})$

Motivație

Verificarea asociativității este una dintre problemele naturale care apar atunci când se lucrează cu tabele Cayley ale diferitelor operații [3] . În special, o astfel de verificare este implementată în sistemele de algebră computerizată GAP [4] și Maple [5] . În cel mai general caz, există operații pentru care toate triplele, cu excepția unuia, sunt asociative - un exemplu de astfel de operație pe elemente este operația astfel încât , și pentru toate celelalte elemente . Singurul său triplu neasociativ este , deoarece [6] . Datorită existenței unor astfel de operații, se poate avea impresia că verificarea asociativității va necesita prelucrarea tuturor triplelor posibile și, prin urmare, o îmbunătățire asimptotică a timpului de rulare a algoritmului este imposibilă [7] . Din același motiv, un algoritm probabilistic naiv care verifică asociativitatea triplelor selectate aleatoriu va necesita verificări pentru a garanta o probabilitate de eroare suficient de mică [8] . Cu toate acestea, algoritmul propus de Rajagopalan și Shulman arată că această estimare poate fi îmbunătățită și servește ca un exemplu clar al modului în care algoritmii probabilistici pot face față problemelor care par dificile pentru algoritmii determiniști - din 2020, algoritmii determiniști rezolvă o anumită problemă în subcubic. timp , necunoscut [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})$

Testul luminii

În 1961, Alfred Clifford și Gordon Preston au publicat în cartea Algebraic Semigroup Theory un test de asociativitate raportat unuia dintre autori de Dr. Light în 1949. Algoritmul constă în a lua în considerare pentru fiecare operație și . Prin definiție, o operație este asociativă dacă și numai dacă (tabelele de operații Cayley sunt aceleași) pentru toate [10] . Light a observat că dacă , adică y are un grup generator , atunci este suficient să se verifice numai pentru [11] [12] . $g\în 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\în G$ $G=\langle S\rangle$ $G$ $S$ $g\în S$

Dacă în definițiile de mai sus și , atunci . $\star _{a}=\circ _{a}$ $\star _{b}=\circ _{b)$ $\star _{a\cdot b}=\circ _{a\cdot b)$

Dovada

Să fie pentru toată lumea . Apoi . ■ $(x\cdot a)\cdot y=x\cdot (a\cdot y)$ $(x\cdot b)\cdot y=x\cdot (b\cdot y)$ $x,y\în 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$

În cel mai rău caz (de exemplu, pentru funcționarea maximă ), cel mai mic set generator de magmă poate fi format din elemente, astfel încât testul va trebui să fie efectuat pentru toate elementele , ceea ce va dura timp. În 1972 , Robert Tarjan a observat că testul lui Light poate fi eficient pentru a testa dacă o anumită operație definește un grup [2] . Acest lucru se datorează faptului că pentru unele tipuri speciale de operații, inclusiv operații care satisfac axioma de grup a prezenței unui element invers , este întotdeauna posibil să se selecteze un set generator de dimensiune mică [12] . ${\textstyle n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Fie ca orice ecuație de formă să aibă o soluție unică (adică un cvasigrup ). Apoi , este posibil să se evidențieze cel mult un set generator de dimensiune . $G$ $a=b\cdot x$ $X$ $G$ $G$ $S$ $\lfloor \log _{2}n\rfloor +1$

Dovada

Să fie un subset astfel încât și . Apoi, datorită faptului că este un cvasigrup, , deoarece toate elementele formei for sunt diferite și nu sunt conținute în . Astfel, adăugarea secvențială la elementele vederii poate fi făcută nu mai mult de o dată. ■ $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$

Prin definiție, este un cvasigrup dacă și numai dacă tabloul său Cayley este un pătrat latin , care poate fi verificat în timp . Aplicarea procedurii descrise mai sus la un cvasigrup permite, la rândul său , să se verifice determinist dacă , este un grup , pentru [13] . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Testul Rajagopalan-Schulman

Primul test subcubic a fost algoritmul de tip Monte Carlo propus în 1996 [14] Sridhar Rajagopalan de la Universitatea Princeton și Leonard Shulman de la Institutul de Tehnologie din Georgia . Procedura propusă de aceștia necesită timp, unde este probabilitatea de eroare maximă admisă [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritm

Algoritmul folosește o algebră de grupă — un spațiu liniar ( algebră ) peste un câmp de dimensiune cu două elemente , ai cărui vectori de bază corespund tuturor elementelor diferite ale magmei . Vectorii unui astfel de spațiu au forma $\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}}

, Unde

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

Au operația de sumă

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

, unde denotă adăugare și în

\oplus

a_{g)

b_{g)

\mathbb {Z} _{2},

precum și funcționarea produsului

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

, unde denotă produsul și în

a_{x}b_{y)

a_{x)

b_{y)

\mathbb {Z} _{2}.

Produsul vectorilor într-o astfel de algebră devine mai intuitiv dacă ne gândim că pentru orice pereche de vectori de bază este definit ca , iar produsul oricărei alte perechi de vectori se obține prin „deschiderea parantezelor” și rearanjarea termenilor. De exemplu, pentru produsul are forma $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}),

iar substituția are ca rezultat o expresie corespunzătoare definiției generale [8] . Pentru algebra definită în acest fel, următoarea lemă este valabilă [15] : $v_{x}\cdot v_{y}=v_{x\cdot y)$

Operația inițială de magmă este asociativă dacă și numai dacă pentru orice . Dacă operația nu este asociativă, atunci probabilitatea ca egalitatea specificată să fie satisfăcută pentru o triplă aleasă uniform aleatoriu nu depășește . $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}}}$

Pentru a verifica asociativitatea se aleg aleatoriu , pentru care . O astfel de verificare poate fi efectuată în timp , iar pentru a obține o probabilitate de eroare care să nu depășească , este suficient să se efectueze verificări, care dă timpul total de rulare [15] . $A,B,C\in \mathbb {Z} _{2}[G]$ $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ $O(n^{2})$ $\delta$ $\log _{8/7}\delta ^{-1)$ ${\textstyle O\left(n^{2}\log \delta ^{-1}\right)}$

Operațiuni arbitrare

Abordarea lui Rajagopalan și Shulman poate fi generalizată pentru a testa identitățile generale, cu condiția ca fiecare variabilă să apară exact o dată în partea stângă și dreaptă a identității [16] .

De exemplu, putem considera o mulțime pe elementele căreia sunt specificate trei operații: „unire” , „intersecție” și „adăugare” . Este necesar să se verifice că . Pentru a face acest lucru, putem lua în considerare operațiile induse $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}

, și

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

și verificați dacă pentru aceste operații în este adevărat . În forma cea mai generală, procedura poate fi caracterizată prin următoarea teoremă [16] : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C))}$

Fie mulțimi finite și o mulțime de operații definite pe produse carteziene finite ale acestor mulțimi astfel încât operația să fie definită pe mulțime , unde este aritatea operației . Apoi verificarea adevărului identității compuse din aceste operații, astfel încât fiecare variabilă să apară în părțile sale din stânga și din dreapta exact o dată, poate fi efectuată în timp , unde este cea mai mare dimensiune posibilă a domeniului de definiție , este numărul total. de operațiuni utilizate în identitate, este numărul total de variabile, este cea mai mare probabilitate de eroare admisă. $D_{1},\dots,D_{k)$ $\circ _{1},\dots ,\circ _{m)$ $\circ _{j}$ $D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j))))$ $c_{j)$ $\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\dreapta)}$ $\circ _{j}$ $l$ $k$ $\delta$

În cazul , operația are un domeniu de dimensiune , și de aceea complexitatea de calcul a procedurii ia forma , în timp ce o verificare naivă ar necesita operații [16] . $|D_{1}|=\dots =|D_{k}|=n$ $\circ _{j}$ $n^{c_{j)}$ $M=n^{\max c_{j)}$ $O(2^{k}ln^{\max c_{j))\log \delta ^{-1})$ $O(ln^{k})$

Acest rezultat poate fi îmbunătățit dacă luăm în considerare algebra pentru un număr prim . În acest caz, conform lemei Schwarz-Zippel , probabilitatea de a respinge o identitate incorectă într-o singură iterație poate fi îmbunătățită de la la , ceea ce corespunde unei probabilități constante pentru și ne permite să îmbunătățim timpul de rulare la [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})$

Caută un martor non-identic

Algoritmul poate fi modificat pentru a găsi un anumit set de variabile pe care identitatea eșuează. De exemplu, luați în considerare căutarea unui triplu non-asociativ în timp . Să se știe pentru unii că . Aceste elemente pot fi asociate cu un triplu , astfel încât dacă , atunci este de asemenea egal cu , iar dacă , atunci este ales aleatoriu între și (în mod similar pentru și ). Pentru probabilitatea ca , estimarea de jos va fi în continuare adevărată , deci procedura se poate repeta până când fiecare dintre elemente are o unitate în doar una dintre poziții, care va corespunde triplu-ului neasociativ dorit în [17] . ${\textstyle (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$ $unu$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $A',B',C'$ $G$

Note

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , p. 120
↑ 1 2 Lipton, Regan, 2013
↑ IsAssociative . _ GAP-Manual de referință . Grupul GAP. Preluat la 1 septembrie 2021. Arhivat din original la 17 aprilie 2021.
↑ IsAssociative . _ Maple Ajutor . maplesoft. Preluat la 14 august 2022. Arhivat din original la 14 aprilie 2021.
↑ 1 2 Rajagopalan, Schulman, 2000 , p. 1162
↑ 12 Sinclair , 2020
↑ 1 2 Matousek, Nešetřil, 2008
↑ Schulman, 2020
↑ Premchand, 1984 , p. 257
↑ Clifford, Preston, 1961 , pp. 7-8
↑ 1 2 Rajagopalan, Schulman, 2000 , pp. 1155-1156
↑ Rajagopalan, Schulman, 2000 , pp. 1160-1161
↑ Rajagopalan, Schulman, 1996
↑ 1 2 Rajagopalan, Schulman, 2000 , pp. 1156-1157
↑ 1 2 3 Rajagopalan, Schulman, 2000 , pp. 1158-1159
↑ Rajagopalan, Schulman, 2000 , pp. 1159-1160

Literatură

Clifford A., Preston G. Testul de asociativitate al lui Light (engleză) // The Algebraic Theory of Semigroups - USA : AMS , 1961. - Vol. 1. - P. 7-8. — 224 p. - ISBN 0-8218-0271-2 - doi:10.1090/SURV/007.1
Lee T., Magniez F., Santha M. Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing (engleză) // Algorithmica - Springer Science + Business Media , 2015. - Vol. 77, Iss. 2. - P. 459-486. — 1302 p. — ISSN 0178-4617 ; 1432-0541 - doi:10.1007/S00453-015-0084-9 - arXiv:1210.1014
Lipton R. J. , Regan K. W. Leonard Schulman: Asociativitatea (engleză) // People, Problems, and Proofs : Essays from Gödel's Lost Letter: 2010 - 2013. - P. 297-299. — 333 p. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Testarea asociativității probabilistice (engleză) // Invitation to Discrete Mathematics - 2 - NYC : OUP , 2008. - P. 388-392. — 443 p. — ISBN 978-0-19-857043-1
Premchand S. Independența axiomelor pentru seturi biordonate (engleză) // Semigroup Forum - Springer Science + Business Media , 1984. - Vol. 28, Iss. 1. - P. 249-263. — 397 p. — ISSN 0037-1912 ; 1432-2137 - doi:10.1007/BF02572487
Rajagopalan S., Schulman L. J. Verificarea identităților // SIAM J. Comput . / M. Sudan - SIAM , 2000. - Vol. 29, Iss. 4. - P. 1155-1163. — 2097 p. — ISSN 0097-5397 ; 1095-7111 - doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verificarea identităților (engleză) // Proceedings of 37th Conference on Foundations of Computer Science - 1996. - 638 p. - ISBN 0-8186-7594-2 - ISSN 0272-5428 - doi:10.1109/SFCS.1996.548520
Schulman L. Verifying Associativity (engleză) // Probability and Algorithms - California Institute of Technology , 2020. - P. 35-37. — 108p.
Sinclair A. Verificarea asociativității (engleză) // Randomness & Computation - UC Berkeley , 2020. - P. 5-6. - 7p.
Tarjan R. E. Determinarea dacă un grupoid este un grup // Informați . proces. Lett. - Elsevier BV , 1972. - Vol. 1, Iss. 3. - P. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9