Перегляд вихідного коду сторінки Тест асоціативності

'''Тест асоціативності'''&nbsp;— перевірка [[Бінарна операція|бінарної операції]] на [[асоціативність]]. Наївна процедура перевірки, яка полягає у переборі всіх можливих трійок аргументів операції, вимагає <math>O(n^3)</math> часу, де <math>n</math>&nbsp;— розмір множини, над яким визначено операцію. Ранні тести асоціативності не давали [[Асимптотичний аналіз|асимптотичних]] покращень порівняно з наївним алгоритмом, проте дозволяли покращити час роботи в окремих випадках. Наприклад, [[Роберт Андре Тарджан|Роберт Тарджан]] 1972 року виявив, що запропонований 1949 року тест Лайта дозволяє виконати перевірку за <math>O(n^2 \log n)</math>, якщо досліджувана бінарна операція оборотна (задає [[Квазігрупа (алгебра)|квазігрупу]]). Перший імовірнісний тест, що покращує час роботи з <math>O(n^3)</math> до <math display="inline">O(n^2 \log \delta^{-1})</math>, був запропонований 1996 року Шрідхаром Раджаґопаланом і {{iw|Леонард Шульман|Леонардом Шульманом||Leonard Schulman}}. 2015 року було запропоновано [[квантовий алгоритм]], що перевіряє операцію на асоціативність за час <math display="inline">O(n^{10/7})</math>, що є поліпшенням у порівнянні з [[Алгоритм Ґровера|пошуком Ґровера]], що працює за <math display="inline">O(n^{3/2})</math><ref>{{Sfn-текст|Lee, Magniez, Santha|2015}}</ref>.

== Постановлення задачі ==
Наведена таблиця розміру <math>n \times n</math>, що описує [[Замикання (математика)|замкнуту]] операцію <math>\cdot : G \times G \mapsto G</math> на множині <math>G</math> розміру <math>n</math>, тобто операція <math>\cdot</math> задана своєю [[Таблиці Келі|таблицею Келі]], а <math>G</math> разом з цією операцією утворює [[Магма (алгебра)|магму]]. Необхідно перевірити, що для будь-яких <math>a, b, c \in G</math> виконано <math>a \cdot (b \cdot c) = (a \cdot b) \cdot c</math> (іншими словами, операція [[Асоціативність|асоціативна]]). Будь-який детермінований алгоритм, який вирішує це завдання, вимагатиме не менше <math>O(n^2)</math> часу, бо кожна чарунка таблиці Келі має бути лічена хоча б раз. Повний перебір всіх трійок <math>a, b, c</math> з перевіркою того, що рівність виконується для кожної трійки, потребує <math>O(n^3)</math> часу<ref name=":2" />.

== Мотивація ==
Перевірка асоціативності&nbsp;— одне з природних завдань, що виникають при роботі з таблицями Келі різних операцій<ref name=":5">{{Sfn-текст|Lipton, Regan|2013}}</ref>. Зокрема, така перевірка вбудована в [[Система комп'ютерної алгебри|системах комп'ютерної алгебри]] [[GAP (система комп'ютерної алгебри))|GAP]]<ref>{{Cite web|lang=en|url=https://www.gap-system.org/Manuals/doc/ref/chap35_mj.html#X7C83B5A47FD18FB7|title=IsAssociative|author=|website=GAP - Reference Manual|date=|publisher=The GAP Group|access-date=2021-09-01|archive-date=2021-04-17|archive-url=https://web.archive.org/web/20210417145512/https://www.gap-system.org/Manuals/doc/ref/chap35_mj.html#X7C83B5A47FD18FB7|deadlink=no}}</ref> і [[Maple]]<ref>{{Cite web|lang=en|url=https://maplesoft.com/support/help/maple/view.aspx?path=Magma%2FIsAssociative|title=IsAssociative|website=Maple Help|publisher=Maplesoft|access-date=2022-08-14|archive-date=2021-04-14|archive-url=https://web.archive.org/web/20210414165058/https://www.maplesoft.com/support/help/Maple/view.aspx?path=Magma%2FIsAssociative|deadlink=no}}</ref>. У найзагальнішому випадку існують операції, для яких усі трійки, крім однієї, є асоціативними&nbsp;— прикладом такої операції на <math>n \geq 3</math> елементах служить операція <math>\cdot</math>, така що <math>1 \cdot 2 = 2</math>, а для всіх інших елементів <math>a \cdot b = 3</math>. Її єдиною неасоціативною трійкою є <math>1,1,2</math>, оскільки <math>1 \cdot (1 \cdot 2) = 1 \cdot 2 = 2 \neq 3 = 3 \cdot 2 = (1 \cdot 1) \cdot 2 </math><ref name=":4" />. Через існування таких операцій може скластися враження, що перевірка асоціативності вимагатиме обробки всіх можливих трійок і тому асимптотичне покращення часу роботи алгоритму неможливе<ref name=":6">{{Sfn-текст|Sinclair|2020}}</ref>. З цієї ж причини наївний імовірнісний алгоритм, що перевіряє асоціативність випадковим чином обраних трійок, вимагатиме <math>O(n^3)</math> перевірок, щоб убезпечити досить низьку ймовірність помилки<ref name=":7">{{Sfn-текст|Matoušek, Nešetřil|2008}}</ref>. Однак запропонований Раджаґопаланом і Шульманом алгоритм показує, що цю оцінку можна покращити, і служить наочним прикладом того, як імовірнісні алгоритми можуть справлятися із завданнями, які виглядають складними для детермінованих алгоритмів&nbsp;— станом на 2020 рік детерміновані алгоритми, що вирішують це завдання за субкубічний час, невідомі<ref>{{Sfn-текст|Schulman|2020}}</ref>.

== Тест Лайта ==
1961 року {{iw|Альфред Кліффорд|||Alfred H. Clifford}} і {{iw|Ґордон Престон|||Gordon Preston}} опублікували у книзі «Алгебраїчна теорія напівгруп» ({{lang-en|The Algebraic Theory of Semigroups}}) тест асоціативності, повідомлений одному з авторів доктором Лайтом 1949 року. Алгоритм полягає у розгляді для кожного <math>g \in G</math> операцій <math>x \star_g y = x \cdot (g \cdot y)</math> і <math>x \circ_g y = (x \cdot g) \cdot y</math>. За визначенням, операція <math>\cdot</math> асоціативна [[Необхідна і достатня умова|якщо і тільки якщо]] <math>\star_g=\circ_g</math> (таблиці Келі операцій збігаються) для всіх <math>g \in G</math><ref>{{Sfn-текст|Premchand|1984|p=257}}</ref>. Лайт звернув увагу, що якщо <math> G = \langle S \rangle</math>, тобто <math>G</math> має [[Породжувальна множина групи|породжувальну множину]] <math>S</math>, то перевірку достатньо провести лише для <math>g \in S</math><ref>{{sfn-текст|Clifford, Preston|1961|pp=7—8}}</ref><ref name=":3" />.

{{Теорема|Якщо у визначеннях вище <math>\star_a=\circ_a</math> і <math>\star_b=\circ_b</math>, то <math>\star_{a \cdot b} = \circ_{a \cdot b}</math>.}}
{{Доведення1|Нехай <math>(x \cdot a) \cdot y = x \cdot (a \cdot y)</math> і <math>(x \cdot b) \cdot y = x \cdot (b \cdot y)</math> для всіх <math>x, y \in G</math>. Тоді <math>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</math>. }}

У гіршому випадку (наприклад, для операції [[Максимальні та мінімальні елементи|максимуму]]) найменша породжувальна множина магми може складатися з <math display="inline">n</math> елементів, тому тест доведеться провести для всіх елементів <math display="inline">G</math>, що займе <math display="inline">O(n^3)</math> часу. 1972 року [[Роберт Андре Тарджан|Роберт Тарджан]] звернув увагу на те, що тест Лайта може бути дієвим для перевірки того, чи задає задана операція [[Група (математика)|групу]]<ref name=":2">{{sfn-текст|Tarjan|1972|p=120}}</ref>. Це пов'язано з тим, що для деяких спеціальних операцій, зокрема операцій, що задовольняють груповій аксіомі наявності [[Зворотний елемент|зворотного елемента]], завжди можна виділити породжувальну множину невеликого розміру<ref name=":3">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1155—1156}}</ref>.

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

{{Доведення1|Нехай <math>T \subset G</math> — деяка підмножина <math>G</math>, така що <math>G \neq \langle T \rangle</math> і <math>b \in G \setminus \langle T \rangle </math>. Тоді, в силу того, що <math>(G, \cdot)</math> квазігрупа, <math>\vert\langle T \cup \{b\} \rangle\vert \geq 2 \vert\langle T\rangle\vert</math>, оскільки всі елементи виду <math>t \cdot b</math> для <math>t \in \langle T\rangle</math> різні і не містяться в <math>\langle T\rangle</math>. Таким чином, послідовне додавання в <math>T \neq \varnothing</math> елементів виду <math>b \in G \setminus \langle T \rangle </math> може бути зроблено не більше <math>\log_2 \vert G \vert</math> разів. }}

За визначенням, <math>G</math> є квазігрупою якщо і тільки якщо її таблиця Келі є [[Латинський квадрат|латинським квадратом]], що може бути перевірено за час <math display="inline">O(n^2)</math>. Застосування до квазігрупи описаної вище процедури дозволяє своєю чергою [[Детермінований алгоритм|детерміновано]] перевірити, чи є <math>G</math> [[Група (математика)|групою]], за <math>O(n^2 \log n)</math><ref>{{sfn-текст|Rajagopalan, Schulman|2000|pp=1160—1161}}</ref>.

== Тест Раджаґопалана&nbsp;— Шульмана ==
Першим субкубічним тестом став [[Клас складності BPP#Алгоритми Монте-Карло|алгоритм типу Монте-Карло]], запропонований 1996 року<ref>{{sfn-текст|Rajagopalan, Schulman|1996}}</ref> Шрідхаром Раджагопаланом з [[Принстонський університет|Принстонського університету]] та {{iw|Леонард Шульман|Леонардом Шульманом||Leonard Schulman}} з [[Технологічний інститут Джорджії|Технологічного інституту Джорджії]]. Запропонована ними процедура вимагає <math>O(n^2 \log \delta^{-1})</math> часу, де <math>\delta</math>&nbsp;— найбільша припустима ймовірність помилки<ref name=":5" /><ref name=":6" />.

=== Алгоритм ===
Алгоритм використовує {{iw|Групоїдна алгебра|групоїдну алгебру|4=Groupoid algebra}} <math>\Z_2[G]</math>&nbsp;— лінійний простір ([[Алгебра над полем|алгебру]]) над двохелементним полем <math>\Z_2</math> розмірності <math>n</math>, базисні вектори <math>v_{g_1}, \dots, v_{g_n}</math> якого відповідають усім різним елементам магми <math>g_1, \dots, g_n</math>. Вектори такого простору мають вигляд

: <math display="inline">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</math>, де <math>a_g \in \Z_2.</math>
Для них визначено операцію суми
: <math display="inline">A + B =
\sum\limits_{g \in G}(a_g \oplus b_g) v_g</math>, де <math>\oplus</math> позначає [[Виключна диз'юнкція|додавання]] <math>a_g</math> і <math>b_g</math> в <math>\Z_2,</math>
а також операція добутку
: <math display="inline">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</math>, де <math>a_x b_y</math> позначає [[Кон'юнкція|добуток]] <math>a_x</math> і <math>b_y</math> у <math>\Z_2.</math>
Добуток векторів у такій алгебрі стає інтуїтивнішим, якщо вважати, що для будь-якої пари базисних векторів він визначений як <math>v_x \cdot v_y = v_{x \cdot y}</math>, а твір будь-якої іншої пари векторів виходить «розкриттям дужок» та перегрупуванням доданків. Наприклад, для <math>G = \{p, q, r\}</math> добуток має вигляд
: <math>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),</math>
а при підстановці <math>v_x \cdot v_y = v_{x \cdot y}</math> виходить вираз, що відповідає загальному визначенню<ref name=":7" />. Для визначеної таким чином алгебри має місце наступна лема<ref name=":0">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1156—1157}}</ref>:

{{Теорема|Операція вихідної магми є асоціативною якщо і тільки якщо <math>A \cdot (B \cdot C) = (A \cdot B) \cdot C</math> для будь-яких <math>A,B,C \in \Z_2[G]</math>. Якщо операція не асоціативна, то ймовірність того, що вказана рівність буде виконана для випадкової рівномірно обраної трійки <math>a, b, c</math>, не перевершує <math display="inline">\frac{7}{8}</math>.}}

Для перевірки асоціативності вибираються випадкові <math>A, B, C \in \Z_2[G]</math>, для котрих перевіряється <math>A \cdot (B \cdot C) = (A \cdot B) \cdot C</math>. Така перевірка може бути здійснена за час <math>O(n^2)</math>, а для досягнення ймовірності помилки, яка не перевищує <math>\delta</math>, достатньо зробити <math>\log_{8/7} \delta^{-1}</math> перевірок, що дає загальний час роботи <math display="inline">O\left(n^2 \log \delta^{-1}\right)</math><ref name=":0" />.

=== Довільні операції ===
Підхід Раджаґопалана і Шульмана може бути узагальнений для перевірки тотожностей загального виду за умови, що кожна змінна зустрічається рівно один раз у лівій та правій частині тотожності<ref name=":1" />.

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

: <math display="inline">A \cup B = \sum\limits_{g \in G} \left( \bigoplus\limits_{x \cup y = g} a_x b_y \right) g</math>, <math display="inline">A \cap B = \sum\limits_{g \in G} \left( \bigoplus\limits_{x \cap y = g} a_x b_y \right) g</math> і <math>\bar A = \sum\limits_{g \in G} \bar a_g g</math>
і перевірити, що для цих операцій у <math>\Z_2[G]</math> вірно <math>\overline{A \cap (B \cup C)} = \overline{A} \cup (\overline{B}\cap \overline C)</math>. У найзагальнішому вигляді процедуру можна охарактеризувати наступною теоремою<ref name=":1">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1158—1159}}</ref>:

{{Теорема|Нехай <math>D_1, \dots, D_k</math> — кінцеві множини, а <math>\circ_1, \dots, \circ_m</math> — набір операцій, визначених над кінцевими [[Декартів добуток множин|декартовими добутками]] цих множин, таких як операція <math>\circ_j</math> визначена на множині <math>D_{\sigma(j, 1)} \times \dots \times D_{\sigma(j, c_j)}</math>, де <math>c_j</math> — [[арність]] операції <math>\circ_j</math>. Тоді перевірка на істинність складеної з цих операцій тотожності, такої, що кожна змінна зустрічається в лівій та правій його частинах рівно один раз, може бути виконана за час <math>O(2^k l M \log\delta^{-1})</math>, де <math display="inline">M=\max_j \left(\vert D_{\sigma(j, 1)}\vert  \cdot \ldots \cdot \vert D_{\sigma(j, c_j)}\vert\right)</math> — найбільший можливий розмір області визначення <math>\circ_j</math>, <math>l</math> — сумарна кількість використаних у тотожності операцій, <math>k</math> — сумарна кількість змінних, <math>\delta</math> — найбільша припустима ймовірність помилки.}}

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

Даний результат може бути поліпшено, якщо замість <math>\Z_2[G]</math> розглядати алгебру <math>\Z_p[G]</math> для простого числа <math>p > k</math>. У такому разі, за {{iw|Лема Шварца — Зіппеля|лемою Шварца — Зіппеля|en|Schwartz–Zippel lemma}}, ймовірність спростування невірної тотожності за одну ітерацію може бути поліпшено з <math display="inline">\frac{1}{2^k}</math> до <math display="inline">1-\frac{k}{p}</math>, що при <math>p \sim (1+\varepsilon)k</math> відповідає константній імовірності <math display="inline">\frac{\varepsilon}{1+\varepsilon}</math> і дозволяє покращити час роботи до <math>O(l M \log\delta^{-1})</math><ref name=":4">{{sfn-текст|Rajagopalan, Schulman|2000|p=1162}}</ref>.

=== Пошук свідка нетотожності ===
Алгоритм може бути модифікований для знаходження конкретного набору змінних, на яких не виконується тотожність. Наприклад, можна розглянути пошук неасоціативної трійки <math display="inline">(a,b,c)</math> за час <math display="inline">O\left(n^2 \log n \log \delta^{-1}\right)</math>. Нехай для деяких <math>A, B, C \in \Z_2[G]</math> відомо, що <math>A \cdot (B \cdot C) \neq (A \cdot B) \cdot C</math>. Цим елементам можна порівняти трійку <math>A', B', C'</math>, таку що якщо <math>a_i=0</math>, то <math>a_i'</math> також дорівнює <math>0</math>, а якщо <math>a_i=1</math>, то <math>a_i'</math> вибирається випадковим чином між <math>0</math> й <math>1</math> (так само для <math>b_i'</math> и <math>c_i'</math>). Для ймовірності того, що <math>A' \cdot (B' \cdot C') \neq (A' \cdot B') \cdot C'</math>, буде все ще правильна оцінка знизу <math display="inline">\frac 1 8</math>, тому процедуру можна повторювати доти, доки кожен з елементів <math>A', B', C'</math> не матиме одиницю лише в одній з позицій, що відповідатиме шуканій неасоціативній трійці в <math>G</math><ref>{{sfn-текст|Rajagopalan, Schulman|2000|pp=1159—1160}}</ref>.

== Примітки ==
{{примітки}}

== Література ==
{{refbegin}}
* {{Cite Q|Q108399966|ref=Clifford, Preston}}
* {{Cite Q|Q107209455|ref=Lee, Magniez, Santha}}
* {{Cite Q|Q107209461|ref=Lipton, Regan}}
* {{Cite Q|Q108399209|ref=Matoušek, Nešetřil}}
* {{Cite Q|Q107212518|ref=Premchand}}
* {{Cite Q|Q107209440|ref=Rajagopalan, Schulman}}
* {{Cite Q|Q107219466|ref=Rajagopalan, Schulman}}
* {{Cite Q|Q108368560|ref=Schulman}}
* {{Cite Q|Q108368950|ref=Sinclair}}
* {{Cite Q|Q107923280|ref=Tarjan}}
{{refend}}

[[Категорія:Абстрактна алгебра]]
[[Категорія:Бінарні операції]]