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

Тест асоціативності — перевірка бінарної операції на асоціативність. Наївна процедура перевірки, яка полягає у переборі всіх можливих трійок аргументів операції, вимагає $O(n^3)$ часу, де $n$ — розмір множини, над яким визначено операцію. Ранні тести асоціативності не давали асимптотичних покращень порівняно з наївним алгоритмом, проте дозволяли покращити час роботи в окремих випадках. Наприклад, Роберт Тарджан 1972 року виявив, що запропонований 1949 року тест Лайта дозволяє виконати перевірку за $O(n^2\log n)$, якщо досліджувана бінарна операція оборотна (задає квазігрупу). Перший імовірнісний тест, що покращує час роботи з $O(n^3)$ до $O(n^2\log {\delta }^{-1})$, був запропонований 1996 року Шрідхаром Раджаґопаланом і Шаблон:Iw. 2015 року було запропоновано квантовий алгоритм, що перевіряє операцію на асоціативність за час $O(n^{10/7})$, що є поліпшенням у порівнянні з пошуком Ґровера, що працює за $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\ge 3$ елементах служить операція $\cdot$, така що $1\cdot 2=2$, а для всіх інших елементів $a\cdot b=3$. Її єдиною неасоціативною трійкою є $1,1,2$, оскільки $1\cdot (1\cdot 2)=1\cdot 2=2\ne 3=3\cdot 2=(1\cdot 1)\cdot 2$. Через існування таких операцій може скластися враження, що перевірка асоціативності вимагатиме обробки всіх можливих трійок і тому асимптотичне покращення часу роботи алгоритму неможливе. З цієї ж причини наївний імовірнісний алгоритм, що перевіряє асоціативність випадковим чином обраних трійок, вимагатиме $O(n^3)$ перевірок, щоб убезпечити досить низьку ймовірність помилки. Однак запропонований Раджаґопаланом і Шульманом алгоритм показує, що цю оцінку можна покращити, і служить наочним прикладом того, як імовірнісні алгоритми можуть справлятися із завданнями, які виглядають складними для детермінованих алгоритмів — станом на 2020 рік детерміновані алгоритми, що вирішують це завдання за субкубічний час, невідомі.

Тест Лайта

1961 року Шаблон:Iw і Шаблон:Iw опублікували у книзі «Алгебраїчна теорія напівгруп» (Шаблон:Lang-en) тест асоціативності, повідомлений одному з авторів доктором Лайтом 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=⟨S⟩$, тобто $G$ має породжувальну множину $S$, то перевірку достатньо провести лише для $g\in S$.

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

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

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

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

Алгоритм

Алгоритм використовує Шаблон:Iw ${\mathbb{Z}}_2[G]$ — лінійний простір (алгебру) над двохелементним полем ${\mathbb{Z}}_2$ розмірності $n$, базисні вектори $v_{g_1},\dots ,v_{g_n}$ якого відповідають усім різним елементам магми $g_1,\dots ,g_n$. Вектори такого простору мають вигляд

$A=a_{g_1}{v}_{g_1}+a_{g_2}{v}_{g_2}+\dots +a_{g_n}{v}_{g_n}=\sum _{g\in G}{a}_g{v}_g$, де $a_g\in {\mathbb{Z}}_2.$

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

$A+B=\sum _{g\in G}(a_g\oplus b_g)v_g$, де $\oplus$ позначає додавання $a_g$ і $b_g$ в ${\mathbb{Z}}_2,$

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

$A\cdot B=\sum _{x,y\in G}{a}_x{b}_y{v}_{x\cdot y}=\sum _{g\in G}(\underset{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,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}$ перевірок, що дає загальний час роботи $O(n^2\log {\delta }^{-1})$.

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

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

Наприклад можна розглянути множину $G$, на елементах якого задано три операції: «об'єднання» $a\cup b$, «перетин» $a\cap b$ і «доповнення» $\overline{a}$. Необхідно перевірити, що $\overline{a\cap (b\cup c)}=\bar{a}\cup (\bar{b}\cap \bar{c})$. Для цього можна розглянути індуковані на ${\mathbb{Z}}_2[G]$ операції

$A\cup B=\sum _{g\in G}\left(\underset{x\cup y=g}{⨁}{a}_x{b}_y\right)g$, $A\cap B=\sum _{g\in G}\left(\underset{x\cap y=g}{⨁}{a}_x{b}_y\right)g$ і $\overline{A}=\sum _{g\in G}{\overline{a}}_{g}g$

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

У випадку $|D_1|=\dots =|D_k|=n$ операція ${\circ }_j$ має область визначення розміру $n^{c_j}$, у зв'язку з чим $M=n^{\max c_j}$ і обчислювальна складність процедури набуває вигляду $O(2^{k}l{n}^{\max c_j}\log {\delta }^{-1})$, тоді як наївна перевірка вимагала б $O(l{n}^k)$ операцій.

Даний результат може бути поліпшено, якщо замість ${\mathbb{Z}}_2[G]$ розглядати алгебру ${\mathbb{Z}}_p[G]$ для простого числа $p>k$. У такому разі, за Шаблон:Iw, ймовірність спростування невірної тотожності за одну ітерацію може бути поліпшено з $\frac{1}{2^k}$ до $1-\frac{k}{p}$, що при $p\sim (1+\epsilon )k$ відповідає константній імовірності $\frac{\epsilon }{1+\epsilon }$ і дозволяє покращити час роботи до $O(lM\log {\delta }^{-1})$.

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

Алгоритм може бути модифікований для знаходження конкретного набору змінних, на яких не виконується тотожність. Наприклад, можна розглянути пошук неасоціативної трійки $(a,b,c)$ за час $O(n^2\log n\log {\delta }^{-1})$. Нехай для деяких $A,B,C\in {\mathbb{Z}}_2[G]$ відомо, що $A\cdot (B\cdot C)\ne (A\cdot B)\cdot C$. Цим елементам можна порівняти трійку $A^{\prime },B^{\prime },C^{\prime }$, таку що якщо $a_i=0$, то ${a_i}^{\prime }$ також дорівнює $0$, а якщо $a_i=1$, то ${a_i}^{\prime }$ вибирається випадковим чином між $0$ й $1$ (так само для ${b_i}^{\prime }$ и ${c_i}^{\prime }$). Для ймовірності того, що $A^{\prime }\cdot (B^{\prime }\cdot C^{\prime })\ne (A^{\prime }\cdot B^{\prime })\cdot C^{\prime }$, буде все ще правильна оцінка знизу $\frac{1}{8}$, тому процедуру можна повторювати доти, доки кожен з елементів $A^{\prime },B^{\prime },C^{\prime }$ не матиме одиницю лише в одній з позицій, що відповідатиме шуканій неасоціативній трійці в $G$.

Література

• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q