Тест ассоциативности — проверка бинарной операции на ассоциативность . Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует ${\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})}$ .

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

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

Мотивация

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

Тест Лайта

В 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}$ . Лайт обратил внимание, что если ${\displaystyle G=\langle S\rangle }$ , то есть у ${\displaystyle G}$ есть порождающее множество ${\displaystyle S}$ , то проверку достаточно произвести лишь для ${\displaystyle g\in S}$ .

Если в определениях выше ${\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 Роберт Тарьян обратил внимание на то, что тест Лайта может быть эффективен для проверки того, задаёт ли заданная операция группу . Это связано с тем, что для некоторых особых типов операций, в том числе операций, удовлетворяющих групповой аксиоме наличия обратного элемента , всегда можно выделить порождающее множество небольшого размера .

Пусть в ${\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)}$ .

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

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

Алгоритм

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

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

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

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

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

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

Данный результат может быть улучшен, если вместо ${\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})}$ .

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

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

Примечания

Литература