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

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

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

Наведена таблиця розміру ${\displaystyle n\times n}$, що описує замкнуту операцію ${\displaystyle \cdot :G\times G\mapsto G}$ на множині ${\displaystyle G}$ розміру ${\displaystyle n}$, тобто операція ${\displaystyle \cdot }$ задана своєю таблицею Келі, а ${\displaystyle G}$ разом з цією операцією утворює магму. Необхідно перевірити, що для будь-яких ${\displaystyle a,b,c\in G}$ виконано ${\displaystyle a\cdot (b\cdot c)=(a\cdot b)\cdot c}$ (іншими словами, операція асоціативна). Будь-який детермінований алгоритм, який вирішує це завдання, вимагатиме не менше ${\displaystyle O(n^{2})}$ часу, бо кожна чарунка таблиці Келі має бути лічена хоча б раз. Повний перебір всіх трійок ${\displaystyle a,b,c}$ з перевіркою того, що рівність виконується для кожної трійки, потребує ${\displaystyle O(n^{3})}$ часу.

Мотивація

Перевірка асоціативності — одне з природних завдань, що виникають при роботі з таблицями Келі різних операцій. Зокрема, така перевірка вбудована в системах комп'ютерної алгебри і Maple. У найзагальнішому випадку існують операції, для яких усі трійки, крім однієї, є асоціативними — прикладом такої операції на ${\displaystyle n\geq 3}$ елементах служить операція ${\displaystyle \cdot }$, така що ${\displaystyle 1\cdot 2=2}$, а для всіх інших елементів ${\displaystyle a\cdot b=3}$. Її єдиною неасоціативною трійкою є ${\displaystyle 1,1,2}$, оскільки ${\displaystyle 1\cdot (1\cdot 2)=1\cdot 2=2\neq 3=3\cdot 2=(1\cdot 1)\cdot 2}$. Через існування таких операцій може скластися враження, що перевірка асоціативності вимагатиме обробки всіх можливих трійок і тому асимптотичне покращення часу роботи алгоритму неможливе. З цієї ж причини наївний імовірнісний алгоритм, що перевіряє асоціативність випадковим чином обраних трійок, вимагатиме ${\displaystyle O(n^{3})}$ перевірок, щоб убезпечити досить низьку ймовірність помилки. Однак запропонований Раджаґопаланом і Шульманом алгоритм показує, що цю оцінку можна покращити, і служить наочним прикладом того, як імовірнісні алгоритми можуть справлятися із завданнями, які виглядають складними для детермінованих алгоритмів — станом на 2020 рік детерміновані алгоритми, що вирішують це завдання за субкубічний час, невідомі.

Тест Лайта

1961 року ^[en] і ^[en] опублікували у книзі «Алгебраїчна теорія напівгруп» (англ. The Algebraic Theory of Semigroups) тест асоціативності, повідомлений одному з авторів доктором Лайтом 1949 року. Алгоритм полягає у розгляді для кожного ${\displaystyle g\in G}$ операцій ${\displaystyle x\star _{g}y=x\cdot (g\cdot y)}$ і ${\displaystyle x\circ _{g}y=(x\cdot g)\cdot y}$. За визначенням, операція ${\displaystyle \cdot }$ асоціативна якщо і тільки якщо ${\displaystyle \star _{g}=\circ _{g}}$ (таблиці Келі операцій збігаються) для всіх ${\displaystyle g\in G}$. Лайт звернув увагу, що якщо ${\displaystyle G=\langle S\rangle }$, тобто ${\displaystyle G}$ має породжувальну множину ${\displaystyle S}$, то перевірку достатньо провести лише для ${\displaystyle g\in S}$.

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

Доведення  

Нехай ${\displaystyle (x\cdot a)\cdot y=x\cdot (a\cdot y)}$ і ${\displaystyle (x\cdot b)\cdot y=x\cdot (b\cdot y)}$ для всіх ${\displaystyle x,y\in G}$. Тоді ${\displaystyle 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 року Роберт Тарджан звернув увагу на те, що тест Лайта може бути дієвим для перевірки того, чи задає задана операція групу. Це пов'язано з тим, що для деяких спеціальних операцій, зокрема операцій, що задовольняють груповій аксіомі наявності зворотного елемента, завжди можна виділити породжувальну множину невеликого розміру.

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

Доведення  

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

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

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

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

Алгоритм

Алгоритм використовує ^[en] ${\displaystyle \mathbb {Z} _{2}[G]}$ — лінійний простір (алгебру) над двохелементним полем ${\displaystyle \mathbb {Z} _{2}}$ розмірності ${\displaystyle n}$, базисні вектори ${\displaystyle v_{g_{1}},\dots ,v_{g_{n}}}$ якого відповідають усім різним елементам магми ${\displaystyle 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}}$, де ${\displaystyle a_{g}\in \mathbb {Z} _{2}.}$

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

${\textstyle A+B=\sum \limits _{g\in G}(a_{g}\oplus b_{g})v_{g}}$, де ${\displaystyle \oplus }$ позначає додавання ${\displaystyle a_{g}}$ і ${\displaystyle b_{g}}$ в ${\displaystyle \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}}$, де ${\displaystyle a_{x}b_{y}}$ позначає добуток ${\displaystyle a_{x}}$ і ${\displaystyle b_{y}}$ у ${\displaystyle \mathbb {Z} _{2}.}$

Добуток векторів у такій алгебрі стає інтуїтивнішим, якщо вважати, що для будь-якої пари базисних векторів він визначений як ${\displaystyle v_{x}\cdot v_{y}=v_{x\cdot y}}$, а твір будь-якої іншої пари векторів виходить «розкриттям дужок» та перегрупуванням доданків. Наприклад, для ${\displaystyle G=\{p,q,r\}}$ добуток має вигляд

${\displaystyle 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}),}$

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

Операція вихідної магми є асоціативною якщо і тільки якщо ${\displaystyle A\cdot (B\cdot C)=(A\cdot B)\cdot C}$ для будь-яких ${\displaystyle A,B,C\in \mathbb {Z} _{2}[G]}$. Якщо операція не асоціативна, то ймовірність того, що вказана рівність буде виконана для випадкової рівномірно обраної трійки ${\displaystyle a,b,c}$, не перевершує ${\textstyle {\frac {7}{8}}}$.

Для перевірки асоціативності вибираються випадкові ${\displaystyle A,B,C\in \mathbb {Z} _{2}[G]}$, для котрих перевіряється ${\displaystyle A\cdot (B\cdot C)=(A\cdot B)\cdot C}$. Така перевірка може бути здійснена за час ${\displaystyle O(n^{2})}$, а для досягнення ймовірності помилки, яка не перевищує ${\displaystyle \delta }$, достатньо зробити ${\displaystyle \log _{8/7}\delta ^{-1}}$ перевірок, що дає загальний час роботи ${\textstyle O\left(n^{2}\log \delta ^{-1}\right)}$.

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

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

Наприклад можна розглянути множину ${\displaystyle G}$, на елементах якого задано три операції: «об'єднання» ${\displaystyle a\cup b}$, «перетин» ${\displaystyle a\cap b}$ і «доповнення» ${\displaystyle {\bar {a}}}$. Необхідно перевірити, що ${\displaystyle {\overline {a\cap (b\cup c)}}={\overline {a}}\cup ({\overline {b}}\cap {\overline {c}})}$. Для цього можна розглянути індуковані на ${\displaystyle \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}$ і ${\displaystyle {\bar {A}}=\sum \limits _{g\in G}{\bar {a}}_{g}g}$

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

Нехай ${\displaystyle D_{1},\dots ,D_{k}}$ — кінцеві множини, а ${\displaystyle \circ _{1},\dots ,\circ _{m}}$ — набір операцій, визначених над кінцевими декартовими добутками цих множин, таких як операція ${\displaystyle \circ _{j}}$ визначена на множині ${\displaystyle D_{\sigma (j,1)}\times \dots \times D_{\sigma (j,c_{j})}}$, де ${\displaystyle c_{j}}$ — арність операції ${\displaystyle \circ _{j}}$. Тоді перевірка на істинність складеної з цих операцій тотожності, такої, що кожна змінна зустрічається в лівій та правій його частинах рівно один раз, може бути виконана за час ${\displaystyle 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}}$, ${\displaystyle l}$ — сумарна кількість використаних у тотожності операцій, ${\displaystyle k}$ — сумарна кількість змінних, ${\displaystyle \delta }$ — найбільша припустима ймовірність помилки.

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

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

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

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

Примітки

1. Lee, Magniez, Santha, 2015
2. Tarjan, 1972, p. 120
3. Lipton, Regan, 2013
4. IsAssociative. GAP - Reference Manual (англ.). The GAP Group. оригіналу за 17 квітня 2021. Процитовано 1 вересня 2021.
5. IsAssociative. Maple Help (англ.). Maplesoft. оригіналу за 14 квітня 2021. Процитовано 14 серпня 2022.
6. Rajagopalan, Schulman, 2000, p. 1162
7. Sinclair, 2020
8. Matoušek, Nešetřil, 2008
9. Schulman, 2020
10. Premchand, 1984, p. 257
11. Clifford, Preston, 1961, pp. 7—8
12. Rajagopalan, Schulman, 2000, pp. 1155—1156
13. Rajagopalan, Schulman, 2000, pp. 1160—1161
14. Rajagopalan, Schulman, 1996
15. Rajagopalan, Schulman, 2000, pp. 1156—1157
16. Rajagopalan, Schulman, 2000, pp. 1158—1159
17. Rajagopalan, Schulman, 2000, pp. 1159—1160

Література

• A. Clifford, G. Preston Light's associativity test // The Algebraic Theory of Semigroups — USA: AMS, 1961. — Vol. 1. — P. 7–8. — 224 p. — — 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 — , 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. —
  d:Track:Q217595d:Track:Q60d:Track:Q472657d:Track:Q956806d:Track:Q108399111d:Track:Q108399209
• S. Premchand Independence of axioms for biordered sets // Semigroup Forum — , 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. — — 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