Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует ${\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 году Шридхаром Раджагопаланом и Леонардом Шульманом^[англ.]. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время ${\textstyle O(n^{10/7})}$, что является улучшением по сравнению с поиском Гровера, работающим за ${\textstyle O(n^{3/2})}$^[1].

Дана таблица размера ${\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})}$ времени^[2].

Проверка ассоциативности — одна из естественных задач, возникающих при работе с таблицами Кэли различных операций^[3]. В частности, такая проверка реализована в системах компьютерной алгебры GAP^[4] и Maple^[5]. В наиболее общем случае, существуют операции, для которых все тройки, кроме одной, являются ассоциативными — примером такой операции на ${\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}$^[6]. Из-за существования таких операций может сложиться впечатление, что проверка ассоциативности потребует обработки всех возможных троек и потому асимптотическое улучшение времени работы алгоритма невозможно^[7]. По этой же причине наивный вероятностный алгоритм, проверяющий ассоциативность случайным образом выбранных троек, потребует ${\displaystyle O(n^{3})}$ проверок, чтобы гарантировать достаточно низкую вероятность ошибки^[8]. Однако предложенный Раджагопаланом и Шульманом алгоритм показывает, что эта оценка может быть улучшена, и служит наглядным примером того, как вероятностные алгоритмы могут справляться с задачами, которые выглядят трудными для детерминированных алгоритмов — по состоянию на 2020 год детерминированные алгоритмы, решающие данную задачу за субкубическое время, неизвестны^[9].

В 1961 году Альфред Клиффорд^[англ.] и Гордон Престон^[англ.] опубликовали в книге «Алгебраическая теория полугрупп» тест ассоциативности, сообщённый одному из авторов доктором Лайтом в 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}$^[10]. Лайт обратил внимание, что если ${\displaystyle G=\langle S\rangle }$, то есть у ${\displaystyle G}$ есть порождающее множество ${\displaystyle S}$, то проверку достаточно произвести лишь для ${\displaystyle g\in S}$^[11][12].

Если в определениях выше ${\displaystyle \star _{a}=\circ _{a}}$ и ${\displaystyle \star _{b}=\circ _{b}}$, то ${\displaystyle \star _{a\cdot b}=\circ _{a\cdot b}}$.

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

Пусть в ${\displaystyle G}$ любое уравнение вида ${\displaystyle a=b\cdot x}$ имеет единственное решение ${\displaystyle x}$ (то есть ${\displaystyle G}$ — квазигруппа). Тогда в ${\displaystyle G}$ можно выделить порождающее множество ${\displaystyle S}$ размером не больше ${\displaystyle \lfloor \log _{2}n\rfloor +1}$.

По определению, ${\displaystyle G}$ является квазигруппой если и только если её таблица Кэли представляет собой латинский квадрат, что может быть проверено за время ${\textstyle O(n^{2})}$. Применение к квазигруппе описанной выше процедуры позволяет в свою очередь детерминированно проверить, является ли ${\displaystyle G}$ группой, за ${\displaystyle O(n^{2}\log n)}$^[13].

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

Алгоритм использует группоидную алгебру^[англ.] ${\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}}$ получается выражение, соответствующее общему определению^[8]. Для определённой таким образом алгебры имеет место следующая лемма^[15]:

Операция исходной магмы ассоциативна если и только если ${\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)}$^[15].

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

Для примера можно рассмотреть множество ${\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}})}$. В наиболее общем виде процедура может быть охарактеризована следующей теоремой^[16]:

Пусть ${\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})}$ операций^[16].

Данный результат может быть улучшен, если вместо ${\displaystyle \mathbb {Z} _{2}[G]}$ рассматривать алгебру ${\displaystyle \mathbb {Z} _{p}[G]}$ для простого числа ${\displaystyle p>k}$. В таком случае, по лемме Шварца — Зиппеля, вероятность опровержения неверного тождества за одну итерацию может быть улучшена с ${\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})}$^[6].

Алгоритм может быть модифицирован для нахождения конкретного набора переменных, на которых тождество не выполняется. Для примера, можно рассмотреть поиск неассоциативной тройки ${\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}$^[17].

Эта статья входит в число хороших статей русскоязычного раздела Википедии.