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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

Література