Test asociativity

Test asociativity - kontrola asociativnosti binární operace . Naivní verifikační procedura, která spočívá ve výčtu všech možných trojic argumentů operace, zabere čas, kde je velikost množiny, nad kterou je operace definována. Časné testy asociativity neposkytly asymptotická zlepšení oproti naivnímu algoritmu, ale v některých speciálních případech zlepšily dobu běhu. Například Robert Tarjan v roce 1972 zjistil, že Lightův test, navržený v roce 1949, umožňuje ověřit, zda je studovaná binární operace vratná (dává kvazigrupu $O(n^{3})$ $n$ $O(n^{2}\log n)$ ). První pravděpodobnostní test, který zlepšuje provozní dobu z do byl navržen v roce 1996 Sridharem Rajagopalanem a Leonardem Shulmanem . V roce 2015 byl navržen kvantový algoritmus , který kontroluje asociativitu operace v čase , což je vylepšení oproti Groverovu vyhledávání , které běží v [1] . $O(n^{3})$ ${\textstyle O(n^{2}\log \delta ^{-1})}$ ${\textstyle O(n^{10/7})}$ ${\textstyle O(n^{3/2})}$

Prohlášení o problému

Je dána tabulka velikostí popisující uzavřenou operaci na množině velikostí , to znamená, že operace je dána její Cayleyovou tabulkou a spolu s touto operací tvoří magma . Je nutné zkontrolovat, zda je u libovolného splněno (jinými slovy operace je asociativní ). Jakýkoli deterministický algoritmus, který řeší tento problém, nebude vyžadovat méně času, protože každou buňku Cayleyovy tabulky je nutné přečíst alespoň jednou. Iterativní výčet všech trojic a kontrola, zda platí rovnost pro každou trojici, zabere čas [2] . $n\krát 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})$

Motivace

Kontrola asociativity je jedním z přirozených problémů, které vznikají při práci s Cayleyho tabulkami různých operací [3] . Zejména je taková kontrola implementována v systémech počítačové algebry GAP [4] a Maple [5] . V nejobecnějším případě existují operace, pro které jsou všechny trojice kromě jedné asociativní - příkladem takové operace s prvky je operace typu , a pro všechny ostatní prvky . Jeho jediná neasociativní trojice je , protože [6] . Vzhledem k existenci takových operací může člověk nabýt dojmu, že kontrola asociativity bude vyžadovat zpracování všech možných trojic, a proto není možné asymptotické zlepšení doby běhu algoritmu [7] . Ze stejného důvodu bude naivní pravděpodobnostní algoritmus, který kontroluje asociativitu náhodně vybraných trojic, vyžadovat kontroly zaručující dostatečně nízkou pravděpodobnost chyby [8] . Algoritmus navržený Rajagopalanem a Shulmanem však ukazuje, že tento odhad lze zlepšit, a slouží jako jasný příklad toho, jak se pravděpodobnostní algoritmy dokážou vypořádat s problémy, které pro deterministické algoritmy vypadají obtížně – od roku 2020 deterministické algoritmy řeší daný problém v subkubickém čas , neznámý [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ův test

V roce 1961 Alfred Clifford a Gordon Preston publikovali v knize Algebraic Semigroup Theory test asociativnosti, který jednomu z autorů oznámil Dr. Light v roce 1949. Algoritmus spočívá v uvažování pro každou operaci a . Podle definice je operace asociativní právě tehdy, když (Cayleyovy tabulky operací jsou stejné) pro všechny [10] . Light si všiml, že pokud má , tedy y generující množinu , stačí zkontrolovat pouze [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$

Pokud ve výše uvedených definicích a , pak . $\star _{a}=\circ _{a}$ ${\displaystyle \star _{b}=\circ _{b))$ ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b))$

Důkaz

Ať je to pro všechny . Pak . ■ $(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$

V nejhorším případě (například pro maximální provoz ) se může nejmenší sada generátorů magmatu skládat z prvků, takže test bude muset být proveden pro všechny prvky , což zabere čas. V roce 1972 si Robert Tarjan všiml, že Lightův test může být účinný pro testování, zda daná operace definuje skupinu [2] . Je to dáno tím, že pro některé speciální typy operací, včetně operací splňujících grupový axiom přítomnosti inverzního prvku , je vždy možné zvolit generující množinu malé velikosti [12] . ${\textstyle n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Nechť jakákoli rovnice tohoto tvaru má jedinečné řešení (tj . kvazigrupu ). Pak je možné vyčlenit generující sadu velikosti maximálně . $G$ $a=b\cdot x$ $X$ $G$ $G$ $S$ $\lfloor \log _{2}n\rpatro +1$

Důkaz

Dovolit být nějaká podmnožina taková, že a . Potom, vzhledem k tomu, že se jedná o kvazigrupu, , protože všechny prvky tvaru for jsou různé a nejsou obsaženy v . Sekvenční přidávání prvků pohledu tedy nelze provést více než jednou. ■ $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$

Podle definice je kvazigrupa právě tehdy, když její Cayleyovo tablo je latinský čtverec , což lze ověřit v čase . Použití výše popsaného postupu na kvazigrupu zase umožňuje deterministicky ověřit, zda , je grupa , pro [13] . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Rajagopalan-Schulmanův test

Prvním subkubickým testem byl algoritmus typu Monte Carlo navržený v roce 1996 [14] Rajagopalanem z Princetonské univerzity a Leonardem Shulmanem z Georgia Institute of Technology . Jimi navrhovaný postup vyžaduje čas, kde je maximální dovolená pravděpodobnost chyby [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritmus

Algoritmus používá grupoidní algebru — lineární prostor ( algebra ) nad dvouprvkovým polem dimenze , jehož základní vektory odpovídají všem různým prvkům magmatu . Vektory takového prostoru mají tvar $\mathbb {Z} _{2}[G]$ $\mathbb{Z } _{2}$ $n$ $v_{g_{1}},\tečky ,v_{g_{n}}$ $g_{1},\tečky ,g_{n}$

{\textstyle A=a_{g_{1}}v_{g_{1}}+a_{g_{2}}v_{g_{2}}+\tečky +a_{g_{n}}v_{g_{n }}=\součet \limits _{g\in G}a_{g}v_{g}}

, kde

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

Mají operaci součtu

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

, kde označuje přidání a in

\oplus

{\displaystyle a_{g))

{\displaystyle b_{g))

\mathbb {Z} _{2},

stejně jako provoz produktu

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

, kde označuje produkt a in

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

{\displaystyle a_{x))

{\displaystyle b_{y))

\mathbb {Z} _{2}.

Součin vektorů v takové algebře se stává intuitivnějším, pokud uvážíme, že pro jakoukoli dvojici základních vektorů je definován jako , a součin jakékoli jiné dvojice vektorů se získá „otevřením závorek“ a přeskupením podmínek. Například pro produkt má tvar ${\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})+\tečky +a_{r}b_{r}(v_{r}\cdot v_{r}),

a substituce vede k výrazu odpovídajícímu obecné definici [8] . Pro takto definovanou algebru platí následující lemma [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

Počáteční operace magmatu je asociativní tehdy a jen tehdy, pokud pro nějakou . Pokud operace není asociativní, pak pravděpodobnost, že zadaná rovnost bude splněna pro náhodně rovnoměrně vybranou trojici , nepřekročí . $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}}}$

Pro kontrolu asociativnosti jsou vybrány náhodné , pro které . Takovou kontrolu lze provést v čase a k dosažení pravděpodobnosti chyby nepřesahující , stačí provést kontroly, které udají celkovou dobu běhu [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)}$

Svévolné operace

Přístup Rajagopalana a Shulmana lze zobecnit pro testování obecných identit za předpokladu, že se každá proměnná vyskytuje přesně jednou na levé a pravé straně identity [16] .

Můžeme například uvažovat množinu , na jejíchž prvcích jsou specifikovány tři operace: "union" , "intersection" a "addition" . Je potřeba to zkontrolovat . K tomu můžeme uvažovat vyvolané operace $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}

a _

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

a zkontrolujte, že pro tyto operace v je pravda . V nejobecnější podobě lze proceduru charakterizovat následující větou [16] : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Dovolit být konečné množiny a být množinou operací definovaných na konečných kartézských součinech těchto množin tak, že operace je definována na množině , kde je arita operace . Pak lze ověření pravdivosti identity složené z těchto operací tak, že se každá proměnná vyskytuje ve své levé a pravé části právě jednou, provést v čase , kde je největší možná velikost definičního oboru , je celkový počet operací použitých v identitě, je celkový počet proměnných, je největší přípustná pravděpodobnost chyby. ${\displaystyle D_{1},\tečky ,D_{k))$ ${\displaystyle \circ _{1},\tečky ,\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$

V případě má operace velikostní doménu , a proto výpočetní složitost procedury nabývá tvaru , zatímco naivní kontrola by vyžadovala operace [16] . $|D_{1}|=\tečky =|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})$

Tento výsledek lze zlepšit, pokud místo toho vezmeme v úvahu algebru pro prvočíslo . V tomto případě lze podle Schwarz-Zippelova lemmatu pravděpodobnost vyvrácení nesprávné identity v jedné iteraci zlepšit z na , což odpovídá konstantní pravděpodobnosti pro a umožňuje nám zlepšit průběžnou dobu na [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})$

Hledání svědka, který není totožný

Algoritmus lze upravit tak, aby našel konkrétní sadu proměnných, u kterých identita selhává. Zvažte například hledání neasociativního trojnásobku v čase . Ať je to u některých znát . Tyto prvky mohou být spojeny s triple , takže if , then je také rovno , a if , then je vybráno náhodně mezi a (podobně pro a ). Pro pravděpodobnost, že , odhad zdola bude stále pravdivý , lze tedy postup opakovat, dokud každý z prvků nebude mít jednotku pouze v jedné z pozic, která bude odpovídat požadovanému neasociativnímu trojici v [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$ $jeden$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $A',B',C'$ $G$

Poznámky

↑ Lee, Magniez, Santha, 2015
↑ 12 Tarjan , 1972 , s. 120
↑ 1 2 Lipton, Regan, 2013
↑ Je Associativní _ Referenční příručka GAP . Skupina GAP. Získáno 1. září 2021. Archivováno z originálu dne 17. dubna 2021.
↑ Je Associativní _ Nápověda Maple . javorový soft. Získáno 14. srpna 2022. Archivováno z originálu dne 14. dubna 2021.
↑ 1 2 Rajagopalan, Schulman, 2000 , str. 1162
↑ 12 Sinclair , 2020
↑ 1 2 Matoušek, Nešetřil, 2008
↑ Schulman, 2020
↑ Premchand, 1984 , s. 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

Literatura

Clifford A., Preston G. Light's associativity test (anglicky) // 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. Vylepšené algoritmy kvantového dotazování pro detekci trojúhelníků a testování asociace (anglicky) // 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: Associativity (anglicky) // People, Problems, and Proofs : Essays from Gödel's 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. Probabilistic associativity testing (anglicky) // 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 bioordered sets (anglicky) // 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. Ověřování identit // SIAM J. Compput . / M. Súdán - SIAM , 2000. - Sv. 29, Iss. 4. - S. 1155-1163. — 2097 s. — ISSN 0097-5397 ; 1095-7111 – doi:10.1137/S0097539797325387
Rajagopalan S., Schulman L. J. Verifying identity (anglicky) // 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 (anglicky) // Probability and Algorithms - California Institute of Technology , 2020. - S. 35-37. — 108p.
Sinclair A. Checking associativity (anglicky) // Randomness & Computation - UC Berkeley , 2020. - S. 5-6. - 7p
Tarjan R. E. Určení, zda je grupoid skupina // Informovat . proces. Lett. - Elsevier BV , 1972. - Sv. 1, Iss. 3. - S. 120-124. — ISSN 0020-0190 ; 1872-6119 – doi:10.1016/0020-0190(72)90012-9