Aszociativitási teszt

Aszociativitási teszt – bináris művelet asszociativitásának ellenőrzése . A naiv ellenőrzési eljárás, amely a műveleti argumentumok összes lehetséges hármasának számbavételéből áll, időt vesz igénybe, ahol annak a halmaznak a mérete, amelyen a művelet definiálva van. A korai asszociativitási tesztek nem nyújtottak aszimptotikus javulást a naiv algoritmushoz képest, de bizonyos speciális esetekben javították a futási időt. Például Robert Tarjan 1972-ben megállapította, hogy az 1949-ben javasolt Light-teszt lehetővé teszi annak ellenőrzését, hogy a vizsgált bináris művelet reverzibilis-e ( kvázicsoportot határoz meg ). Sridhar Rajagopalan és Leonard Shulman 1996-ban javasolta az első valószínűségi tesztet, amely től- ig javítja a futási időt . 2015-ben javasoltak egy kvantumalgoritmust , amely időben ellenőrzi a művelet asszociativitását , ami előrelépés a Grover-féle kereséshez képest , amely [1] -ben fut . $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})}$

A probléma leírása

Adott egy mérettáblázat , amely leír egy zárt műveletet egy mérethalmazon , azaz a műveletet a Cayley tábla adja meg , és ezzel a művelettel együtt magmát alkot . Ellenőrizni kell, hogy bármelyik esetén teljesül -e (más szóval, a művelet asszociatív ). Bármely determinisztikus algoritmus, amely ezt a problémát megoldja, nem kevesebb időt igényel , mivel a Cayley-tábla minden celláját legalább egyszer el kell olvasni. Az összes hármas iteratív felsorolása , annak ellenőrzése, hogy minden hármasra érvényes-e az egyenlőség, időbe telik [2] . $n\szer n$ $\cdot :G\times G\mapsto G$ $G$ $n$ $\cdot$ $G$ ${\megjelenítési stílus a,b,c\in G}$ $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ $O(n^{2})$ $ABC$ $O(n^{3})$

Motiváció

Az asszociativitás ellenőrzése az egyik természetes probléma, amely a különféle műveletek Cayley tábláival való munka során felmerül [3] . Egy ilyen ellenőrzést különösen a GAP [4] és a Maple [5] számítógépes algebrai rendszerben valósítanak meg . A legáltalánosabb esetben vannak olyan műveletek, amelyeknél egy kivételével a hármasok mindegyike asszociatív – ilyen elemekre vonatkozó művelet például az olyan művelet, hogy , és az összes többi elem esetében . Egyetlen nem asszociatív hármasa a , mert [6] . Az ilyen műveletek megléte miatt az a benyomás alakulhat ki, hogy az asszociativitás-ellenőrzés az összes lehetséges hármas feldolgozását igényli, ezért az algoritmus futási idejének aszimptotikus javítása lehetetlen [7] . Ugyanezen okból kifolyólag egy naiv valószínűségi algoritmus, amely a véletlenszerűen kiválasztott hármasok asszociativitását ellenőrzi, ellenőrzéseket igényel, hogy garantálja a kellően alacsony hibavalószínűséget [8] . A Rajagopalan és Shulman által javasolt algoritmus azonban azt mutatja, hogy ez a becslés javítható, és világos példa arra, hogy a valószínűségi algoritmusok hogyan tudnak megbirkózni a determinisztikus algoritmusok számára nehéznek tűnő problémákkal – 2020-tól a determinisztikus algoritmusok szubkubikusan oldanak meg egy adott problémát. idő , ismeretlen [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})$

Fényteszt

Alfred Clifford és Gordon Preston 1961- ben az Algebraic Semigroup Theory című könyvben közzétett egy asszociativitástesztet, amelyről Dr. Light 1949-ben beszámolt az egyik szerzőnek. Az algoritmus abból áll, hogy minden egyes műveletre és . Definíció szerint egy művelet akkor és csak akkor asszociatív (a műveletek Cayley táblái ugyanazok) minden [10] esetén . Light észrevette, hogy ha , azaz y -nak van generátorkészlete , akkor elegendő csak a [11] [12] esetén ellenőrizni . $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$

Ha a fenti definíciókban és , akkor . $\star _{a}=\circ _{a}$ ${\displaystyle \star _{b}=\circ _{b))$ ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b))$

Bizonyíték

Legyen mindenkié . _ Akkor . ■ $(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$

A legrosszabb esetben (például a maximális működés érdekében ) a legkisebb magmagenerátor készlet elemekből is állhat , így a tesztet minden elemre el kell végezni , ami időbe telik. 1972 -ben Robert Tarjan észrevette, hogy a Light tesztje hatékony lehet annak tesztelésére, hogy egy adott művelet meghatároz-e egy csoportot [2] . Ez annak a ténynek köszönhető, hogy néhány speciális művelettípushoz, beleértve azokat a műveleteket is, amelyek kielégítik az inverz elem jelenlétének csoportaxiómáját , mindig lehetőség van egy kis méretű generátorkészlet kiválasztására [12] . ${\textstyle n}$ ${\textstyle G}$ ${\textstyle O(n^{3})}$

Legyen bármely alakú egyenletnek egyedi megoldása ( vagyis kvázicsoportja ). Ekkor legfeljebb egy méretű generátorkészletet lehet kiemelni . $G$ $a=b\cdot x$ $x$ $G$ $G$ $S$ $\lfloor \log _{2}n\rfloor +1$

Bizonyíték

Legyen olyan részhalmaz , hogy és . Aztán annak a ténynek köszönhetően, hogy ez egy kvázicsoport, mivel a for form minden eleme különböző, és nem szerepel a -ban . Így a nézet elemeinek szekvenciális kiegészítése legfeljebb egyszer végezhető el. ■ $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$

Definíció szerint kvázicsoport akkor és csak akkor, ha Cayley tablója egy latin négyzet , ami időben ellenőrizhető . A fent leírt eljárás kvázicsoportra történő alkalmazása viszont lehetővé teszi annak determinisztikus ellenőrzését, hogy , csoport -e [13] esetén . $G$ ${\textstyle O(n^{2})}$ $G$ $O(n^{2}\log n)$

Rajagopalan-Schulman teszt

Az első szubkubikus teszt a Monte Carlo típusú algoritmus volt, 1996-ban javasoltak [14] Sridhar Rajagopalan, a Princeton Egyetem és Leonard Shulman , a Georgia Institute of Technology munkatársa . Az általuk javasolt eljárás időigényes, ahol a megengedett legnagyobb hibavalószínűség [3] [7] . $O(n^{2}\log \delta ^{-1})$ $\delta$

Algoritmus

Az algoritmus egy csoportoid algebrát használ – egy lineáris teret ( algebrát ) egy kételemű dimenziómező felett , amelynek bázisvektorai a magma összes különböző elemének felelnek meg . Egy ilyen tér vektorainak alakja van $\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}}+\pontok +a_{g_{n}}v_{g_{n }}=\sum \limits _{g\in G}a_{g}v_{g}}

, ahol

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

Náluk van az összegművelet

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

, ahol az összeadást és az in-t jelöli

\oplus

{\displaystyle a_{g))

{\displaystyle b_{g))

\mathbb {Z} _{2},

valamint a termék működését

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

, ahol a terméket jelöli és in

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

{\displaystyle a_{x))

{\displaystyle b_{y))

\mathbb {Z} _{2}.

A vektorok szorzata egy ilyen algebrában intuitívabbá válik, ha figyelembe vesszük, hogy bármely bázisvektorpár esetén ez a következőképpen van definiálva: , és bármely másik vektorpár szorzata a "zárójelek kinyitásával" és a tagok átrendezésével érhető el. Például a terméknek van formája ${\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}),

a helyettesítés pedig az általános definíciónak megfelelő kifejezést eredményez [8] . Az így definiált algebrára a következő lemma érvényes [15] : ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y))$

A kezdeti magma művelet akkor és csak akkor asszociatív, ha bármelyik esetén . Ha a művelet nem asszociatív, akkor annak a valószínűsége, hogy a megadott egyenlőség teljesül egy véletlenszerűen választott hármasra , nem haladja meg a -t . $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ $A,B,C\in \mathbb {Z} _{2}[G]$ $ABC$ ${\textstyle {\frac {7}{8}}}$

Az asszociativitás ellenőrzésére véletlenszerűeket választunk , amelyekhez . Az ilyen ellenőrzés időben elvégezhető , és a ,-ot meg nem haladó hibavalószínűség eléréséhez elegendő ellenőrzéseket végezni, ami megadja a teljes futási időt [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}\jobbra)}$

Önkényes műveletek

Rajagopalan és Shulman megközelítése általánosítható az általános azonosságok tesztelésére, feltéve, hogy minden változó pontosan egyszer fordul elő az azonosság bal és jobb oldalán [16] .

Tekinthetünk például egy halmazt , amelynek elemein három művelet van megadva: "union" , "intersection" és "addition" . Ezt ellenőrizni kell . Ehhez figyelembe vesszük az indukált műveleteket $G$ $a\cup b$ $a\cap b$ ${\bár {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}

, és

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

és ellenőrizze, hogy ezekre a műveletekre igaz -e . A legáltalánosabb formában az eljárás a következő [16] tétellel jellemezhető : $\mathbb {Z} _{2}[G]$ ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C)))$

Legyenek véges halmazok, és e halmazok véges derékszögű szorzataira definiált műveletek halmaza úgy, hogy a művelet a halmazon legyen definiálva , ahol a művelet aritása . Ekkor az ezekből a műveletekből összeállított azonosság valódiságának ellenőrzése úgy, hogy minden változó a bal és jobb részében pontosan egyszer forduljon elő, időben elvégezhető , ahol a definíciós tartomány lehető legnagyobb mérete a teljes szám Az identitásban használt műveletek száma a változók teljes száma, a legnagyobb megengedett hibavalószínűség. ${\displaystyle D_{1},\dots ,D_{k))$ ${\displaystyle \circ _{1},\dots ,\circ _{m))$ $\circ _{j}$ ${\displaystyle D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j)))))$ ${\displaystyle 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\right)}$ $\circ _{j}$ $l$ $k$ $\delta$

Abban az esetben, ha a műveletnek mérettartománya van , ezért az eljárás számítási bonyolultsága a formát ölti , míg a naiv ellenőrzéshez műveletekre lenne szükség [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})$

Ez az eredmény javítható, ha ehelyett egy prímszám algebráját vesszük figyelembe . Ebben az esetben a Schwarz-Zippel lemma szerint a hibás azonosság megcáfolásának valószínűsége egy iterációban -ról -ra javítható , ami egy állandó valószínűségnek felel meg, és lehetővé teszi a futási idő javítását [6] -ra . $\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})$

Nem személyazonosságú tanú keresése

Az algoritmus módosítható, hogy megkeressen egy adott változókészletet, amelynél az identitás sikertelen. Fontolja meg például egy nem asszociatív hármas keresését az időben . Legyen tudomásul egyesek számára, hogy . Ezeket az elemeket egy hármashoz társíthatjuk úgy, hogy ha , akkor egyenlő a -val , és ha , akkor véletlenszerűen kerül kiválasztásra a és között (hasonlóan a és -hez ). Annak valószínűségére, hogy az alulról származó becslés továbbra is igaz lesz , így az eljárás addig ismételhető, amíg mindegyik elemnek csak az egyik pozíciójában van olyan egysége, amely megfelel a kívánt nem asszociatív hármasnak a [17]-ben . ${\textstyle (a,b,c)}$ ${\textstyle O\left(n^{2}\log n\log \delta ^{-1}\jobbra)}$ $A,B,C\in \mathbb {Z} _{2}[G]$ $A\cdot (B\cdot C)\neq (A\cdot B)\cdot C$ $ABC'$ $a_{i}=0$ $a_{i}'$ $0$ $a_{i}=1$ $a_{i}'$ $0$ $egy$ $b_{i}'$ $c_{i}'$ $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$ ${\textstyle {\frac {1}{8}}}$ $ABC'$ $G$

Jegyzetek

↑ Lee, Magniez, Santha, 2015
↑ Tarján 12. , 1972 , p. 120
↑ 1 2 Lipton, Regan, 2013
↑ IsAssociative _ _ GAP-Reference Manual . A GAP Csoport. Letöltve: 2021. szeptember 1. Az eredetiből archiválva : 2021. április 17.
↑ IsAssociative _ _ Maple Help . juharsoft. Letöltve: 2022. augusztus 14. Az eredetiből archiválva : 2021. április 14.
↑ 1 2 Rajagopalan, Schulman, 2000 , p. 1162
↑ Sinclair 12. , 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

Irodalom

Clifford A., Preston G. Light's asssociativity test (angol) // 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 (angol) // 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: Associativity (angol) // Emberek, problémák és bizonyítékok : Esszék Gödel elveszett leveléből: 2010 - 2013. - P. 297-299. — 333 p. doi:10.1007/ 978-3-642-41422-0_57
Matoušek J. , Nešetřil J. Valószínűségi asszociativitásvizsgálat (angol) // Meghívás diszkrét matematikára - 2 - NYC : OUP , 2008. - P. 388-392. — 443 p. — ISBN 978-0-19-857043-1
Premchand S. Axiómák függetlensége biorendezett halmazokhoz (angol) // 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. Identities Verification of Identities // 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. Verifying Identities (angol) // 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. Az asszociativitás ellenőrzése (angol) // Valószínűség és algoritmusok - California Institute of Technology , 2020. - 35-37. o. — 108p.
Sinclair A. Az asszociativitás ellenőrzése (angol) // Randomness & Computation - UC Berkeley , 2020. - 5-6. o. - 7p.
Tarjan R. E. Annak meghatározása, hogy egy grupoid csoport-e // Inform . folyamat. Lett. - Elsevier BV , 1972. - 1. évf. 1, Iss. 3. - P. 120-124. — ISSN 0020-0190 ; 1872-6119 - doi:10.1016/0020-0190(72)90012-9