Тест ассоциативности — Википедия

Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует времени, где  — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за , если исследуемая бинарная операция обратима (задаёт квазигруппу). Первый вероятностный тест, улучшающий время работы с до , был предложен в 1996 году Шридхаром Раджагопаланом и Леонардом Шульманом[en]. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время , что является улучшением по сравнению с поиском Гровера, работающим за [1].

Постановка задачи[править | править код]

Дана таблица размера , описывающая замкнутую операцию на множестве размера , то есть операция задана своей таблицей Кэли, а вместе с данной операцией образует магму. Необходимо проверить, что для любых выполнено (другими словами, операция ассоциативна). Любой детерминированный алгоритм, решающий данную задачу, потребует не менее времени, так как каждая ячейка таблицы Кэли должна быть считана хотя бы раз. Полный перебор всех троек с проверкой того, что равенство выполняется для каждой тройки, требует времени[2].

Мотивация[править | править код]

Проверка ассоциативности — одна из естественных задач, возникающих при работе с таблицами Кэли различных операций[3]. В частности, такая проверка реализована в системах компьютерной алгебры GAP[4] и Maple[5]. В наиболее общем случае, существуют операции, для которых все тройки, кроме одной, являются ассоциативными — примером такой операции на элементах служит операция , такая что , а для всех остальных элементов . Её единственной неассоциативной тройкой является , так как [6]. Из-за существования таких операций может сложиться впечатление, что проверка ассоциативности потребует обработки всех возможных троек и потому асимптотическое улучшение времени работы алгоритма невозможно[7]. По этой же причине наивный вероятностный алгоритм, проверяющий ассоциативность случайным образом выбранных троек, потребует проверок, чтобы гарантировать достаточно низкую вероятность ошибки[8]. Однако предложенный Раджагопаланом и Шульманом алгоритм показывает, что эта оценка может быть улучшена, и служит наглядным примером того, как вероятностные алгоритмы могут справляться с задачами, которые выглядят трудными для детерминированных алгоритмов — по состоянию на 2020 год детерминированные алгоритмы, решающие данную задачу за субкубическое время, неизвестны[9].

Тест Лайта[править | править код]

В 1961 году Альфред Клиффорд[en] и Гордон Престон[en] опубликовали в книге «Алгебраическая теория полугрупп» тест ассоциативности, сообщённый одному из авторов доктором Лайтом в 1949 году. Алгоритм заключается в рассмотрении для каждого операций и . По определению, операция ассоциативна если и только если (таблицы Кэли операций совпадают) для всех [10]. Лайт обратил внимание, что если , то есть у есть порождающее множество , то проверку достаточно произвести лишь для [11][12].

Если в определениях выше и , то .

В худшем случае (например, для операции максимума) наименьшее порождающее множества магмы может состоять из элементов, потому тест придётся провести для всех элементов , что займёт времени. В 1972 Роберт Тарьян обратил внимание на то, что тест Лайта может быть эффективен для проверки того, задаёт ли заданная операция группу[2]. Это связано с тем, что для некоторых особых типов операций, в том числе операций, удовлетворяющих групповой аксиоме наличия обратного элемента, всегда можно выделить порождающее множество небольшого размера[12].

Пусть в любое уравнение вида имеет единственное решение (то есть квазигруппа). Тогда в можно выделить порождающее множество размером не больше .

По определению, является квазигруппой если и только если её таблица Кэли представляет собой латинский квадрат, что может быть проверено за время . Применение к квазигруппе описанной выше процедуры позволяет в свою очередь детерминированно проверить, является ли группой, за [13].

Тест Раджагопалана — Шульмана[править | править код]

Первым субкубическим тестом стал алгоритм типа Монте-Карло, предложенный в 1996 году[14] Шридхаром Раджагопаланом из Принстонского университета и Леонардом Шульманом[en] из Технологического института Джорджии. Предложенная ими процедура требует времени, где  — наибольшая допустимая вероятность ошибки[3][7].

Алгоритм[править | править код]

Алгоритм использует группоидную алгебру[en]  — линейное пространство (алгебру) над двухэлементным полем размерности , базисные векторы которого соответствуют всем различным элементам магмы . Векторы такого пространства имеют вид

, где

Для них определена операция суммы

, где обозначает сложение и в

а также операция произведения

, где обозначает произведение и в

Произведение векторов в такой алгебре становится более интуитивным, если считать, что для любой пары базисных векторов оно определено как , а произведение любой другой пары векторов получается «раскрытием скобок» и перегруппировкой слагаемых. Например, для произведение имеет вид

а при подстановке получается выражение, соответствующее общему определению[8]. Для определённой таким образом алгебры имеет место следующая лемма[15]:

Операция исходной магмы ассоциативна если и только если для любых . Если операция не ассоциативна, то вероятность того, что указанное равенство будет выполнено для случайной равномерно выбранной тройки , не превосходит .

Для проверки ассоциативности выбираются случайные , для которых проверяется . Такая проверка может быть осуществлена за время , а для достижения вероятности ошибки, не превосходящей , достаточно сделать проверок, что даёт общее время работы [15].

Произвольные операции[править | править код]

Подход Раджагопалана и Шульмана может быть обобщён для проверки тождеств общего вида при условии, что каждая переменная встречается ровно один раз в левой и правой части тождества[16].

Для примера можно рассмотреть множество , на элементах которого заданы три операции: «объединение» , «пересечение» и «дополнение» . Необходимо проверить, что . Для этого можно рассмотреть индуцированные на операции

, и

и проверить, что для этих операций в верно . В наиболее общем виде процедура может быть охарактеризована следующей теоремой[16]:

Пусть — конечные множества, а — набор операций, определённых над конечными декартовыми произведениями этих множеств, таких что операция определена на множестве , где арность операции . Тогда проверка на истинность составленного из этих операций тождества, такого что каждая переменная встречается в левой и правой его частях ровно один раз, может быть выполнена за время , где — наибольший возможный размер области определения , — суммарное число использованных в тождестве операций, — суммарное число переменных, — наибольшая допустимая вероятность ошибки.

В случае операция имеет область определения размера , в связи с чем и вычислительная сложность процедуры приобретает вид , в то время как наивная проверка потребовала бы операций[16].

Данный результат может быть улучшен, если вместо рассматривать алгебру для простого числа . В таком случае, по лемме Шварца — Зиппеля, вероятность опровержения неверного тождества за одну итерацию может быть улучшена с до , что при соответствует константной вероятности и позволяет улучшить время работы до [6].

Поиск свидетеля нетождественности[править | править код]

Алгоритм может быть модифицирован для нахождения конкретного набора переменных, на которых тождество не выполняется. Для примера, можно рассмотреть поиск неассоциативной тройки за время . Пусть для некоторых известно, что . Данным элементам можно сопоставить тройку , такую что если , то также равно , а если , то выбирается случайным образом между и (аналогично для и ). Для вероятности того, что , будет всё ещё верна оценка снизу , потому процедуру можно повторять до тех пор, пока каждый из элементов не будет иметь единицу лишь в одной из позиций, что будет соответствовать искомой неассоциативной тройке в [17].

Примечания[править | править код]

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

Литература[править | править код]