Тест ассоциативности

Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует $O(n^3)$ времени, где $n$ — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за $O(n^2\log n)$, если исследуемая бинарная операция обратима (задаёт квазигруппу). Первый вероятностный тест, улучшающий время работы с $O(n^3)$ до $O(n^2\log {\delta }^{-1})$, был предложен в 1996 году Шридхаром Раджагопаланом и Шаблон:Не переведено 5. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время $O(n^{10/7})$, что является улучшением по сравнению с поиском Гровера, работающим за $O(n^{3/2})$.

Постановка задачи

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

Мотивация

Проверка ассоциативности — одна из естественных задач, возникающих при работе с таблицами Кэли различных операций. В частности, такая проверка реализована в системах компьютерной алгебры GAP и Maple. В наиболее общем случае, существуют операции, для которых все тройки, кроме одной, являются ассоциативными — примером такой операции на $n\ge 3$ элементах служит операция $\cdot$, такая что $1\cdot 2=2$, а для всех остальных элементов $a\cdot b=3$. Её единственной неассоциативной тройкой является $1,1,2$, так как $1\cdot (1\cdot 2)=1\cdot 2=2\ne 3=3\cdot 2=(1\cdot 1)\cdot 2$. Из-за существования таких операций может сложиться впечатление, что проверка ассоциативности потребует обработки всех возможных троек и потому асимптотическое улучшение времени работы алгоритма невозможно. По этой же причине наивный вероятностный алгоритм, проверяющий ассоциативность случайным образом выбранных троек, потребует $O(n^3)$ проверок, чтобы гарантировать достаточно низкую вероятность ошибки. Однако предложенный Раджагопаланом и Шульманом алгоритм показывает, что эта оценка может быть улучшена, и служит наглядным примером того, как вероятностные алгоритмы могут справляться с задачами, которые выглядят трудными для детерминированных алгоритмов — по состоянию на 2020 год детерминированные алгоритмы, решающие данную задачу за субкубическое время, неизвестны.

Тест Лайта

В 1961 году Шаблон:Не переведено 5 и Шаблон:Не переведено 5 опубликовали в книге «Алгебраическая теория полугрупп» тест ассоциативности, сообщённый одному из авторов доктором Лайтом в 1949 году. Алгоритм заключается в рассмотрении для каждого $g\in G$ операций $x{\star }_{g}y=x\cdot (g\cdot y)$ и $x{\circ }_{g}y=(x\cdot g)\cdot y$. По определению, операция $\cdot$ ассоциативна если и только если ${\star }_g={\circ }_g$ (таблицы Кэли операций совпадают) для всех $g\in G$. Лайт обратил внимание, что если $G=⟨S⟩$, то есть у $G$ есть порождающее множество $S$, то проверку достаточно произвести лишь для $g\in S$.

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

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

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

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

Алгоритм

Алгоритм использует Шаблон:Не переведено 5 ${\mathbb{Z}}_2[G]$ — линейное пространство (алгебру) над двухэлементным полем ${\mathbb{Z}}_2$ размерности $n$, базисные векторы $v_{g_1},\dots ,v_{g_n}$ которого соответствуют всем различным элементам магмы $g_1,\dots ,g_n$. Векторы такого пространства имеют вид

$A=a_{g_1}{v}_{g_1}+a_{g_2}{v}_{g_2}+\dots +a_{g_n}{v}_{g_n}=\sum _{g\in G}{a}_g{v}_g$, где $a_g\in {\mathbb{Z}}_2.$

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

$A+B=\sum _{g\in G}(a_g\oplus b_g)v_g$, где $\oplus$ обозначает сложение $a_g$ и $b_g$ в ${\mathbb{Z}}_2,$

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

$A\cdot B=\sum _{x,y\in G}{a}_x{b}_y{v}_{x\cdot y}=\sum _{g\in G}(\underset{x\cdot y=g}{⨁}{a}_x{b}_y)v_g$, где $a_x{b}_y$ обозначает произведение $a_x$ и $b_y$ в ${\mathbb{Z}}_2.$

Произведение векторов в такой алгебре становится более интуитивным, если считать, что для любой пары базисных векторов оно определено как $v_x\cdot v_y=v_{x\cdot y}$, а произведение любой другой пары векторов получается «раскрытием скобок» и перегруппировкой слагаемых. Например, для $G=\{p,q,r\}$ произведение имеет вид

$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),$

а при подстановке $v_x\cdot v_y=v_{x\cdot y}$ получается выражение, соответствующее общему определению. Для определённой таким образом алгебры имеет место следующая лемма:

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

Произвольные операции

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

Для примера можно рассмотреть множество $G$, на элементах которого заданы три операции: «объединение» $a\cup b$, «пересечение» $a\cap b$ и «дополнение» $\overline{a}$. Необходимо проверить, что $\overline{a\cap (b\cup c)}=\bar{a}\cup (\bar{b}\cap \bar{c})$. Для этого можно рассмотреть индуцированные на ${\mathbb{Z}}_2[G]$ операции

$A\cup B=\sum _{g\in G}\left(\underset{x\cup y=g}{⨁}{a}_x{b}_y\right)g$, $A\cap B=\sum _{g\in G}\left(\underset{x\cap y=g}{⨁}{a}_x{b}_y\right)g$ и $\overline{A}=\sum _{g\in G}{\overline{a}}_{g}g$

и проверить, что для этих операций в ${\mathbb{Z}}_2[G]$ верно $\overline{A\cap (B\cup C)}=\bar{A}\cup (\bar{B}\cap \bar{C})$. В наиболее общем виде процедура может быть охарактеризована следующей теоремой:

В случае $|D_1|=\dots =|D_k|=n$ операция ${\circ }_j$ имеет область определения размера $n^{c_j}$, в связи с чем $M=n^{\max c_j}$ и вычислительная сложность процедуры приобретает вид $O(2^{k}l{n}^{\max c_j}\log {\delta }^{-1})$, в то время как наивная проверка потребовала бы $O(l{n}^k)$ операций.

Данный результат может быть улучшен, если вместо ${\mathbb{Z}}_2[G]$ рассматривать алгебру ${\mathbb{Z}}_p[G]$ для простого числа $p>k$. В таком случае, по лемме Шварца — Зиппеля, вероятность опровержения неверного тождества за одну итерацию может быть улучшена с $\frac{1}{2^k}$ до $1-\frac{k}{p}$, что при $p\sim (1+\epsilon )k$ соответствует константной вероятности $\frac{\epsilon }{1+\epsilon }$ и позволяет улучшить время работы до $O(lM\log {\delta }^{-1})$.

Поиск свидетеля нетождественности

Алгоритм может быть модифицирован для нахождения конкретного набора переменных, на которых тождество не выполняется. Для примера, можно рассмотреть поиск неассоциативной тройки $(a,b,c)$ за время $O(n^2\log n\log {\delta }^{-1})$. Пусть для некоторых $A,B,C\in {\mathbb{Z}}_2[G]$ известно, что $A\cdot (B\cdot C)\ne (A\cdot B)\cdot C$. Данным элементам можно сопоставить тройку $A^{\prime },B^{\prime },C^{\prime }$, такую что если $a_i=0$, то ${a_i}^{\prime }$ также равно $0$, а если $a_i=1$, то ${a_i}^{\prime }$ выбирается случайным образом между $0$ и $1$ (аналогично для ${b_i}^{\prime }$ и ${c_i}^{\prime }$). Для вероятности того, что $A^{\prime }\cdot (B^{\prime }\cdot C^{\prime })\ne (A^{\prime }\cdot B^{\prime })\cdot C^{\prime }$, будет всё ещё верна оценка снизу $\frac{1}{8}$, потому процедуру можно повторять до тех пор, пока каждый из элементов $A^{\prime },B^{\prime },C^{\prime }$ не будет иметь единицу лишь в одной из позиций, что будет соответствовать искомой неассоциативной тройке в $G$.

Литература

• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q
• Шаблон:Cite Q