Тест асоціативності

Тест асоціативності — перевірка бінарної операції на асоціативність. Наївна процедура перевірки, яка полягає у переборі всіх можливих трійок аргументів операції, вимагає $O(n^{3})$ часу, де $n$ — розмір множини, над яким визначено операцію. Ранні тести асоціативності не давали асимптотичних покращень порівняно з наївним алгоритмом, проте дозволяли покращити час роботи в окремих випадках. Наприклад, Роберт Тарджан 1972 року виявив, що запропонований 1949 року тест Лайта дозволяє виконати перевірку за $O(n^{2}\log n)$, якщо досліджувана бінарна операція оборотна (задає квазігрупу). Перший імовірнісний тест, що покращує час роботи з $O(n^{3})$ до ${\textstyle O(n^{2}\log \delta ^{-1})}$, був запропонований 1996 року Шрідхаром Раджаґопаланом і Леонардом Шульманом. 2015 року було запропоновано квантовий алгоритм, що перевіряє операцію на асоціативність за час ${\textstyle O(n^{10/7})}$, що є поліпшенням у порівнянні з пошуком Ґровера, що працює за ${\textstyle O(n^{3/2})}$.

Постановлення задачі

Наведена таблиця розміру $n\times 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})$ часу.

Мотивація

Перевірка асоціативності — одне з природних завдань, що виникають при роботі з таблицями Келі різних операцій. Зокрема, така перевірка вбудована в системах комп'ютерної алгебри GAP і Maple. У найзагальнішому випадку існують операції, для яких усі трійки, крім однієї, є асоціативними — прикладом такої операції на $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})$ перевірок, щоб убезпечити досить низьку ймовірність помилки. Однак запропонований Раджаґопаланом і Шульманом алгоритм показує, що цю оцінку можна покращити, і служить наочним прикладом того, як імовірнісні алгоритми можуть справлятися із завданнями, які виглядають складними для детермінованих алгоритмів — станом на 2020 рік детерміновані алгоритми, що вирішують це завдання за субкубічний час, невідомі.

Тест Лайта

1961 року Альфред Кліффорд і Ґордон Престон опублікували у книзі «Алгебраїчна теорія напівгруп» (англ. The Algebraic Theory of Semigroups) тест асоціативності, повідомлений одному з авторів доктором Лайтом 1949 року. Алгоритм полягає у розгляді для кожного $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$.

Якщо у визначеннях вище $\star _{a}=\circ _{a}$ і $\star _{b}=\circ _{b}$, то $\star _{a\cdot b}=\circ _{a\cdot b}$.

Доведення  

Нехай $(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$. ■

У гіршому випадку (наприклад, для операції максимуму) найменша породжувальна множина магми може складатися з ${\textstyle n}$ елементів, тому тест доведеться провести для всіх елементів ${\textstyle G}$, що займе ${\textstyle O(n^{3})}$ часу. 1972 року Роберт Тарджан звернув увагу на те, що тест Лайта може бути дієвим для перевірки того, чи задає задана операція групу. Це пов'язано з тим, що для деяких спеціальних операцій, зокрема операцій, що задовольняють груповій аксіомі наявності зворотного елемента, завжди можна виділити породжувальну множину невеликого розміру.

Нехай у $G$ будь-яке рівняння виду $a=b\cdot x$ має єдине рішення $x$ (тобто $G$ — квазігрупа). Тоді в $G$ можна виділити породжувальну множину $S$ розміром не більше $\lfloor \log _{2}n\rfloor +1$.

Доведення  

Нехай $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$ разів. ■

За визначенням, $G$ є квазігрупою якщо і тільки якщо її таблиця Келі є латинським квадратом, що може бути перевірено за час ${\textstyle O(n^{2})}$. Застосування до квазігрупи описаної вище процедури дозволяє своєю чергою детерміновано перевірити, чи є $G$ групою, за $O(n^{2}\log n)$.

Тест Раджаґопалана — Шульмана

Першим субкубічним тестом став алгоритм типу Монте-Карло, запропонований 1996 року Шрідхаром Раджагопаланом з Принстонського університету та Леонардом Шульманом з Технологічного інституту Джорджії. Запропонована ними процедура вимагає $O(n^{2}\log \delta ^{-1})$ часу, де $\delta$ — найбільша припустима ймовірність помилки.

Алгоритм

Алгоритм використовує групоїдну алгебру $\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}}$, де $a_{g}\in \mathbb {Z} _{2}.$

Для них визначено операцію суми

${\textstyle A+B=\sum \limits _{g\in G}(a_{g}\oplus b_{g})v_{g}}$, де $\oplus$ позначає додавання $a_{g}$ і $b_{g}$ в $\mathbb {Z} _{2},$

а також операція добутку

${\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}}$, де $a_{x}b_{y}$ позначає добуток $a_{x}$ і $b_{y}$ у $\mathbb {Z} _{2}.$

Добуток векторів у такій алгебрі стає інтуїтивнішим, якщо вважати, що для будь-якої пари базисних векторів він визначений як $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}),$

а при підстановці $v_{x}\cdot v_{y}=v_{x\cdot y}$ виходить вираз, що відповідає загальному визначенню. Для визначеної таким чином алгебри має місце наступна лема:

Операція вихідної магми є асоціативною якщо і тільки якщо $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}}}$.

Для перевірки асоціативності вибираються випадкові $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)}$.

Довільні операції

Підхід Раджаґопалана і Шульмана може бути узагальнений для перевірки тотожностей загального виду за умови, що кожна змінна зустрічається рівно один раз у лівій та правій частині тотожності.

Наприклад можна розглянути множину $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}$, ${\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$

і перевірити, що для цих операцій у $\mathbb {Z} _{2}[G]$ вірно ${\overline {A\cap (B\cup C)}}={\overline {A}}\cup ({\overline {B}}\cap {\overline {C}})$. У найзагальнішому вигляді процедуру можна охарактеризовати наступною теоремою:

Нехай $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 \right)}$ — найбільший можливий розмір області визначення $\circ _{j}$, $l$ — сумарна кількість використаних у тотожності операцій, $k$ — сумарна кількість змінних, $\delta$ — найбільша припустима ймовірність помилки.

У випадку $|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})$ операцій.

Даний результат може бути поліпшено, якщо замість $\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})$.

Пошук свідка нетотожності

Алгоритм може бути модифікований для знаходження конкретного набору змінних, на яких не виконується тотожність. Наприклад, можна розглянути пошук неасоціативної трійки ${\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$ и $1$ (так само для $b_{i}'$ и $c_{i}'$). Для ймовірності того, що $A'\cdot (B'\cdot C')\neq (A'\cdot B')\cdot C'$, буде все ще правильна оцінка знизу ${\textstyle {\frac {1}{8}}}$, тому процедуру можна повторювати доти, доки кожен із елементів $A',B',C'$ не матиме одиницю лише в одній з позицій, що відповідатиме шуканій неасоціативній трійці в $G$.

Література

• A. Clifford, G. Preston Light's associativity test // 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
  d:Track:Q107209435d:Track:Q108399966d:Track:Q30d:Track:Q465654
• Lee T., Magniez F., Santha M. Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing // 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
  d:Track:Q2835897d:Track:Q107209455d:Track:Q176916
• Lipton R. J. Leonard Schulman: Associativity // 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
  d:Track:Q7326742d:Track:Q107209465d:Track:Q107209461
• Matoušek J., Nešetřil J. Probabilistic associativity testing // Invitation to Discrete Mathematics — 2 — NYC: OUP, 2008. — P. 388–392. — 443 p. — ISBN 978-0-19-857043-1
  d:Track:Q217595d:Track:Q60d:Track:Q472657d:Track:Q956806d:Track:Q108399111d:Track:Q108399209
• S. Premchand Independence of axioms for biordered sets // 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
  d:Track:Q176916d:Track:Q3478426d:Track:Q107212518
• Rajagopalan S., Schulman L. J. 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
  d:Track:Q7390263d:Track:Q107209440d:Track:Q782100d:Track:Q93149
• S. Rajagopalan, Schulman L. J. Verifying identities // 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
  d:Track:Q107219466d:Track:Q54008518
• Schulman L. Verifying Associativity // Probability and Algorithms — California Institute of Technology, 2020. — P. 35–37. — 108 p.
  d:Track:Q108368560d:Track:Q161562d:Track:Q18012457d:Track:Q108368532
• Sinclair A. Checking associativity // Randomness & Computation — UC Berkeley, 2020. — P. 5–6. — 7 p.
  d:Track:Q4306813d:Track:Q168756d:Track:Q108368920d:Track:Q108368950
• Tarjan R. E. Determining whether a groupoid is a group // Inform. Process. Lett. — Elsevier BV, 1972. — Vol. 1, Iss. 3. — P. 120–124. — ISSN 0020-0190; 1872-6119 — doi:10.1016/0020-0190(72)90012-9
  d:Track:Q746413d:Track:Q107923280d:Track:Q129239