Тест асоціативності — перевірка бінарної операції на асоціативність. Наївна процедура перевірки, яка полягає у переборі всіх можливих трійок аргументів операції, вимагає  часу, де  — розмір множини, над яким визначено операцію. Ранні тести асоціативності не давали асимптотичних покращень порівняно з наївним алгоритмом, проте дозволяли покращити час роботи в окремих випадках. Наприклад, Роберт Тарджан 1972 року виявив, що запропонований 1949 року тест Лайта дозволяє виконати перевірку за , якщо досліджувана бінарна операція оборотна (задає квазігрупу). Перший імовірнісний тест, що покращує час роботи з  до , був запропонований 1996 року Шрідхаром Раджаґопаланом і . 2015 року було запропоновано , що перевіряє операцію на асоціативність за час , що є поліпшенням у порівнянні з пошуком Ґровера, що працює за .

Постановлення задачі
Наведена таблиця розміру , що описує замкнуту операцію  на множині  розміру , тобто операція  задана своєю таблицею Келі, а  разом з цією операцією утворює магму. Необхідно перевірити, що для будь-яких  виконано  (іншими словами, операція асоціативна). Будь-який детермінований алгоритм, який вирішує це завдання, вимагатиме не менше  часу, бо кожна чарунка таблиці Келі має бути лічена хоча б раз. Повний перебір всіх трійок  з перевіркою того, що рівність виконується для кожної трійки, потребує  часу.

Мотивація
Перевірка асоціативності — одне з природних завдань, що виникають при роботі з таблицями Келі різних операцій. Зокрема, така перевірка вбудована в системах комп'ютерної алгебри GAP і Maple. У найзагальнішому випадку існують операції, для яких усі трійки, крім однієї, є асоціативними — прикладом такої операції на  елементах служить операція , така що , а для всіх інших елементів . Її єдиною неасоціативною трійкою є , оскільки . Через існування таких операцій може скластися враження, що перевірка асоціативності вимагатиме обробки всіх можливих трійок і тому асимптотичне покращення часу роботи алгоритму неможливе. З цієї ж причини наївний імовірнісний алгоритм, що перевіряє асоціативність випадковим чином обраних трійок, вимагатиме  перевірок, щоб убезпечити досить низьку ймовірність помилки. Однак запропонований Раджаґопаланом і Шульманом алгоритм показує, що цю оцінку можна покращити, і служить наочним прикладом того, як імовірнісні алгоритми можуть справлятися із завданнями, які виглядають складними для детермінованих алгоритмів — станом на 2020 рік детерміновані алгоритми, що вирішують це завдання за субкубічний час, невідомі.

Тест Лайта
1961 року  і  опублікували у книзі «Алгебраїчна теорія напівгруп» () тест асоціативності, повідомлений одному з авторів доктором Лайтом 1949 року. Алгоритм полягає у розгляді для кожного  операцій  і . За визначенням, операція  асоціативна якщо і тільки якщо  (таблиці Келі операцій збігаються) для всіх . Лайт звернув увагу, що якщо , тобто  має породжувальну множину , то перевірку достатньо провести лише для .




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





За визначенням,  є квазігрупою якщо і тільки якщо її таблиця Келі є латинським квадратом, що може бути перевірено за час . Застосування до квазігрупи описаної вище процедури дозволяє своєю чергою детерміновано перевірити, чи є  групою, за .

Тест Раджаґопалана — Шульмана
Першим субкубічним тестом став алгоритм типу Монте-Карло, запропонований 1996 року Шрідхаром Раджагопаланом з Принстонського університету та  з Технологічного інституту Джорджії. Запропонована ними процедура вимагає  часу, де  — найбільша припустима ймовірність помилки.

Алгоритм
Алгоритм використовує   — лінійний простір (алгебру) над двохелементним полем  розмірності , базисні вектори  якого відповідають усім різним елементам магми . Вектори такого простору мають вигляд

: , де 
Для них визначено операцію суми
: , де  позначає додавання  і  в 
а також операція добутку
: , де  позначає добуток  і  у 
Добуток векторів у такій алгебрі стає інтуїтивнішим, якщо вважати, що для будь-якої пари базисних векторів він визначений як , а твір будь-якої іншої пари векторів виходить «розкриттям дужок» та перегрупуванням доданків. Наприклад, для  добуток має вигляд
: 
а при підстановці  виходить вираз, що відповідає загальному визначенню. Для визначеної таким чином алгебри має місце наступна лема:



Для перевірки асоціативності вибираються випадкові , для котрих перевіряється . Така перевірка може бути здійснена за час , а для досягнення ймовірності помилки, яка не перевищує , достатньо зробити  перевірок, що дає загальний час роботи .

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

Наприклад можна розглянути множину , на елементах якого задано три операції: «об'єднання» , «перетин»  і «доповнення» . Необхідно перевірити, що . Для цього можна розглянути індуковані на  операції

: ,  і 
і перевірити, що для цих операцій у  вірно . У найзагальнішому вигляді процедуру можна охарактеризовати наступною теоремою:



У випадку  операція  має область визначення розміру , у зв'язку з чим  і обчислювальна складність процедури набуває вигляду , тоді як наївна перевірка вимагала би  операцій.

Даний результат може бути поліпшено, якщо замість  розглядати алгебру  для простого числа . У такому разі, за , ймовірність спростування невірної тотожності за одну ітерацію може бути поліпшено з  до , що при  відповідає константній вірогідності  і дозволяє покращити час роботи до .

Пошук свідка нетотожності
Алгоритм може бути модифікований для знаходження конкретного набору змінних, на яких не виконується тотожність. Наприклад, можна розглянути пошук неасоціативної трійки  за час . Нехай для деяких  відомо, що . Цим елементам можна порівняти трійку , таку що якщо , то  також дорівнює , а якщо , то  вибирається випадковим чином між  и  (так само для  и ). Для ймовірності того, що , буде все ще правильна оцінка знизу , тому процедуру можна повторювати доти, доки кожен із елементів  не матиме одиницю лише в одній з позицій, що відповідатиме шуканій неасоціативній трійці в .

Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 



