Просмотр кода страницы Тест ассоциативности

'''Тест ассоциативности''' — проверка [[Бинарная операция|бинарной операции]] на [[Ассоциативность (математика)|ассоциативность]]. Наивная процедура проверки, заключающаяся в [[Полный перебор|переборе]] всех возможных троек аргументов операции, требует <math>O(n^3)</math> времени, где <math>n</math> — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали [[Асимптотика|асимптотических]] улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, [[Тарьян, Роберт|Роберт Тарьян]] в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за <math>O(n^2 \log n)</math>, если исследуемая бинарная операция обратима (задаёт [[Квазигруппа (математика)|квазигруппу]]). Первый вероятностный тест, улучшающий время работы с <math>O(n^3)</math> до <math display="inline">O(n^2 \log \delta^{-1})</math>, был предложен в 1996 году Шридхаром Раджагопаланом и {{Не переведено 5|Шульман, Леонард|Леонардом Шульманом||Leonard Schulman}}. В 2015 году был предложен [[квантовый алгоритм]], проверяющий операцию на ассоциативность за время <math display="inline">O(n^{10/7})</math>, что является улучшением по сравнению с [[Алгоритм Гровера|поиском Гровера]], работающим за <math display="inline">O(n^{3/2})</math><ref>{{Sfn-текст|Lee, Magniez, Santha|2015}}</ref>.

== Постановка задачи ==
Дана таблица размера <math>n \times n</math>, описывающая [[Замыкание (алгебра)|замкнутую]] операцию <math>\cdot : G \times G \mapsto G</math> на множестве <math>G</math> размера <math>n</math>, то есть операция <math>\cdot</math> задана своей [[Таблица Кэли|таблицей Кэли]], а <math>G</math> вместе с данной операцией образует [[Магма (алгебра)|магму]]. Необходимо проверить, что для любых <math>a, b, c \in G</math> выполнено <math>a \cdot (b \cdot c) = (a \cdot b) \cdot c</math> (другими словами, операция [[Ассоциативность (математика)|ассоциативна]]). Любой детерминированный алгоритм, решающий данную задачу, потребует не менее <math>O(n^2)</math> времени, так как каждая ячейка таблицы Кэли должна быть считана хотя бы раз. [[Полный перебор]] всех троек <math>a, b, c</math> с проверкой того, что равенство выполняется для каждой тройки, требует <math>O(n^3)</math> времени<ref name=":2" />.

== Мотивация ==
Проверка ассоциативности — одна из естественных задач, возникающих при работе с [[Таблица Кэли|таблицами Кэли]] различных операций<ref name=":5">{{Sfn-текст|Lipton, Regan|2013}}</ref>. В частности, такая проверка реализована в [[Система компьютерной алгебры|системах компьютерной алгебры]] [[GAP (система компьютерной алгебры)|GAP]]<ref>{{Cite web|lang=en|url=https://www.gap-system.org/Manuals/doc/ref/chap35_mj.html#X7C83B5A47FD18FB7|title=IsAssociative|author=|website=GAP - Reference Manual|date=|publisher=The GAP Group|access-date=2021-09-01|archive-date=2021-04-17|archive-url=https://web.archive.org/web/20210417145512/https://www.gap-system.org/Manuals/doc/ref/chap35_mj.html#X7C83B5A47FD18FB7|deadlink=no}}</ref> и [[Maple]]<ref>{{Cite web|lang=en|url=https://maplesoft.com/support/help/maple/view.aspx?path=Magma%2FIsAssociative|title=IsAssociative|website=Maple Help|publisher=Maplesoft|access-date=2022-08-14|archive-date=2021-04-14|archive-url=https://web.archive.org/web/20210414165058/https://www.maplesoft.com/support/help/Maple/view.aspx?path=Magma%2FIsAssociative|deadlink=no}}</ref>. В наиболее общем случае, существуют операции, для которых все тройки, кроме одной, являются ассоциативными — примером такой операции на <math>n \geq 3</math> элементах служит операция <math>\cdot</math>, такая что <math>1 \cdot 2 = 2</math>, а для всех остальных элементов <math>a \cdot b = 3</math>. Её единственной неассоциативной тройкой является <math>1,1,2</math>, так как <math>1 \cdot (1 \cdot 2) = 1 \cdot 2 = 2 \neq 3 = 3 \cdot 2 = (1 \cdot 1) \cdot 2 </math><ref name=":4" />. Из-за существования таких операций может сложиться впечатление, что проверка ассоциативности потребует обработки всех возможных троек и потому асимптотическое улучшение времени работы алгоритма невозможно<ref name=":6">{{Sfn-текст|Sinclair|2020}}</ref>. По этой же причине наивный вероятностный алгоритм, проверяющий ассоциативность случайным образом выбранных троек, потребует <math>O(n^3)</math> проверок, чтобы гарантировать достаточно низкую вероятность ошибки<ref name=":7">{{Sfn-текст|Matoušek, Nešetřil|2008}}</ref>. Однако предложенный Раджагопаланом и Шульманом алгоритм показывает, что эта оценка может быть улучшена, и служит наглядным примером того, как вероятностные алгоритмы могут справляться с задачами, которые выглядят трудными для детерминированных алгоритмов — по состоянию на 2020 год детерминированные алгоритмы, решающие данную задачу за субкубическое время, неизвестны<ref>{{Sfn-текст|Schulman|2020}}</ref>.

== Тест Лайта ==
В 1961 году {{Не переведено 5|Клиффорд, Альфред|Альфред Клиффорд||Alfred H. Clifford}} и {{Не переведено 5|Престон, Гордон|Гордон Престон||Gordon Preston}} опубликовали в книге «Алгебраическая теория полугрупп» тест ассоциативности, сообщённый одному из авторов доктором Лайтом в 1949 году. Алгоритм заключается в рассмотрении для каждого <math>g \in G</math> операций <math>x \star_g y = x \cdot (g \cdot y)</math> и <math>x \circ_g y = (x \cdot g) \cdot y</math>. По определению, операция <math>\cdot</math> ассоциативна [[Необходимое и достаточное условия|если и только если]] <math>\star_g=\circ_g</math> (таблицы Кэли операций совпадают) для всех <math>g \in G</math><ref>{{Sfn-текст|Premchand|1984|p=257}}</ref>. Лайт обратил внимание, что если <math> G = \langle S \rangle</math>, то есть у <math>G</math> есть [[Порождающее множество группы|порождающее множество]] <math>S</math>, то проверку достаточно произвести лишь для <math>g \in S</math><ref>{{sfn-текст|Clifford, Preston|1961|pp=7—8}}</ref><ref name=":3" />.

{{Теорема|Если в определениях выше <math>\star_a=\circ_a</math> и <math>\star_b=\circ_b</math>, то <math>\star_{a \cdot b} = \circ_{a \cdot b}</math>.}}
{{Доказательство|Пусть <math>(x \cdot a) \cdot y = x \cdot (a \cdot y)</math> и <math>(x \cdot b) \cdot y = x \cdot (b \cdot y)</math> для всех <math>x, y \in G</math>. Тогда <math>x \cdot ((a \cdot b) \cdot y) = x \cdot (a \cdot (b \cdot y)) = (x \cdot a) \cdot (b \cdot y) = ((x \cdot a) \cdot b) \cdot y = (x \cdot (a \cdot b)) \cdot y</math>. }}

В худшем случае (например, для операции [[Максимальные и минимальные элементы|максимума]]) наименьшее порождающее множества магмы может состоять из <math display="inline">n</math> элементов, потому тест придётся провести для всех элементов <math display="inline">G</math>, что займёт <math display="inline">O(n^3)</math> времени. В 1972 [[Тарьян, Роберт|Роберт Тарьян]] обратил внимание на то, что тест Лайта может быть эффективен для проверки того, задаёт ли заданная операция [[Группа (математика)|группу]]<ref name=":2">{{sfn-текст|Tarjan|1972|p=120}}</ref>. Это связано с тем, что для некоторых особых типов операций, в том числе операций, удовлетворяющих групповой аксиоме наличия [[Обратный элемент|обратного элемента]], всегда можно выделить порождающее множество небольшого размера<ref name=":3">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1155—1156}}</ref>.

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

{{Доказательство|Пусть <math>T \subset G</math> — некоторое подмножество <math>G</math>, такое что <math>G \neq \langle T \rangle</math> и <math>b \in G \setminus \langle T \rangle </math>. Тогда, в силу того, что <math>(G, \cdot)</math> квазигруппа, <math>\vert\langle T \cup \{b\} \rangle\vert \geq 2 \vert\langle T\rangle\vert</math>, так как все элементы вида <math>t \cdot b</math> для <math>t \in \langle T\rangle</math> различны и не содержатся в <math>\langle T\rangle</math>. Таким образом, последовательное добавление в <math>T \neq \varnothing</math> элементов вида <math>b \in G \setminus \langle T \rangle </math> может быть произведено не более <math>\log_2 \vert G \vert</math> раз. }}

По определению, <math>G</math> является квазигруппой если и только если её таблица Кэли представляет собой [[латинский квадрат]], что может быть проверено за время <math display="inline">O(n^2)</math>. Применение к квазигруппе описанной выше процедуры позволяет в свою очередь [[Детерминированный алгоритм|детерминированно]] проверить, является ли <math>G</math> [[Группа (математика)|группой]], за <math>O(n^2 \log n)</math><ref>{{sfn-текст|Rajagopalan, Schulman|2000|pp=1160—1161}}</ref>.

== Тест Раджагопалана — Шульмана ==
Первым субкубическим тестом стал [[Алгоритм Монте-Карло|алгоритм типа Монте-Карло]], предложенный в 1996 году<ref>{{sfn-текст|Rajagopalan, Schulman|1996}}</ref> Шридхаром Раджагопаланом из [[Принстонский университет|Принстонского университета]] и {{Не переведено 5|Шульман, Леонард|Леонардом Шульманом||Leonard Schulman}} из [[Технологический институт Джорджии|Технологического института Джорджии]]. Предложенная ими процедура требует <math>O(n^2 \log \delta^{-1})</math> времени, где <math>\delta</math> — наибольшая допустимая вероятность ошибки<ref name=":5" /><ref name=":6" />.

=== Алгоритм ===
Алгоритм использует {{Не переведено 5|Группоидная алгебра|группоидную алгебру|4=Groupoid algebra}} <math>\Z_2[G]</math> — линейное пространство ([[Алгебра над полем|алгебру]]) над [[Конечное поле#Поле из двух элементов|двухэлементным полем]] <math>\Z_2</math> размерности <math>n</math>, базисные векторы <math>v_{g_1}, \dots, v_{g_n}</math> которого соответствуют всем различным элементам магмы <math>g_1, \dots, g_n</math>. Векторы такого пространства имеют вид

: <math display="inline">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</math>, где <math>a_g \in \Z_2.</math>
Для них определена операция суммы
: <math display="inline">A + B =
\sum\limits_{g \in G}(a_g \oplus b_g) v_g</math>, где <math>\oplus</math> обозначает [[Исключающее «или»|сложение]] <math>a_g</math> и <math>b_g</math> в <math>\Z_2,</math>
а также операция произведения
: <math display="inline">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</math>, где <math>a_x b_y</math> обозначает [[Конъюнкция|произведение]] <math>a_x</math> и <math>b_y</math> в <math>\Z_2.</math>
Произведение векторов в такой алгебре становится более интуитивным, если считать, что для любой пары базисных векторов оно определено как <math>v_x \cdot v_y = v_{x \cdot y}</math>, а произведение любой другой пары векторов получается «раскрытием скобок» и перегруппировкой слагаемых. Например, для <math>G = \{p, q, r\}</math> произведение имеет вид
: <math>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),</math>
а при подстановке <math>v_x \cdot v_y = v_{x \cdot y}</math> получается выражение, соответствующее общему определению<ref name=":7" />. Для определённой таким образом алгебры имеет место следующая лемма<ref name=":0">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1156—1157}}</ref>:

{{Теорема|Операция исходной магмы ассоциативна если и только если <math>A \cdot (B \cdot C) = (A \cdot B) \cdot C</math> для любых <math>A,B,C \in \Z_2[G]</math>. Если операция не ассоциативна, то вероятность того, что указанное равенство будет выполнено для случайной равномерно выбранной тройки <math>a, b, c</math>, не превосходит <math display="inline">\frac{7}{8}</math>.}}

Для проверки ассоциативности выбираются случайные <math>A, B, C \in \Z_2[G]</math>, для которых проверяется <math>A \cdot (B \cdot C) = (A \cdot B) \cdot C</math>. Такая проверка может быть осуществлена за время <math>O(n^2)</math>, а для достижения вероятности ошибки, не превосходящей <math>\delta</math>, достаточно сделать <math>\log_{8/7} \delta^{-1}</math> проверок, что даёт общее время работы <math display="inline">O\left(n^2 \log \delta^{-1}\right)</math><ref name=":0" />.

=== Произвольные операции ===
Подход Раджагопалана и Шульмана может быть обобщён для проверки тождеств общего вида при условии, что каждая переменная встречается ровно один раз в левой и правой части тождества<ref name=":1" />.

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

: <math display="inline">A \cup B = \sum\limits_{g \in G} \left( \bigoplus\limits_{x \cup y = g} a_x b_y \right) g</math>, <math display="inline">A \cap B = \sum\limits_{g \in G} \left( \bigoplus\limits_{x \cap y = g} a_x b_y \right) g</math> и <math>\bar A = \sum\limits_{g \in G} \bar a_g g</math>
и проверить, что для этих операций в <math>\Z_2[G]</math> верно <math>\overline{A \cap (B \cup C)} = \overline{A} \cup (\overline{B}\cap \overline C)</math>. В наиболее общем виде процедура может быть охарактеризована следующей теоремой<ref name=":1">{{sfn-текст|Rajagopalan, Schulman|2000|pp=1158—1159}}</ref>:

{{Теорема|Пусть <math>D_1, \dots, D_k</math> — конечные множества, а <math>\circ_1, \dots, \circ_m</math> — набор операций, определённых над конечными декартовыми произведениями этих множеств, таких что операция <math>\circ_j</math> определена на множестве <math>D_{\sigma(j, 1)} \times \dots \times D_{\sigma(j, c_j)}</math>, где <math>c_j</math> — [[арность]] операции <math>\circ_j</math>. Тогда проверка на истинность составленного из этих операций тождества, такого что каждая переменная встречается в левой и правой его частях ровно один раз, может быть выполнена за время <math>O(2^k l M \log\delta^{-1})</math>, где <math display="inline">M=\max_j \left(\vert D_{\sigma(j, 1)}\vert  \cdot \ldots \cdot \vert D_{\sigma(j, c_j)}\vert\right)</math> — наибольший возможный размер области определения <math>\circ_j</math>, <math>l</math> — суммарное число использованных в тождестве операций, <math>k</math> — суммарное число переменных, <math>\delta</math> — наибольшая допустимая вероятность ошибки.}}

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

Данный результат может быть улучшен, если вместо <math>\Z_2[G]</math> рассматривать алгебру <math>\Z_p[G]</math> для простого числа <math>p > k</math>. В таком случае, по [[Лемма Шварца — Зиппеля|лемме Шварца — Зиппеля]], вероятность опровержения неверного тождества за одну итерацию может быть улучшена с <math display="inline">\frac{1}{2^k}</math> до <math display="inline">1-\frac{k}{p}</math>, что при <math>p \sim (1+\varepsilon)k</math> соответствует константной вероятности <math display="inline">\frac{\varepsilon}{1+\varepsilon}</math> и позволяет улучшить время работы до <math>O(l M \log\delta^{-1})</math><ref name=":4">{{sfn-текст|Rajagopalan, Schulman|2000|p=1162}}</ref>.

=== Поиск свидетеля нетождественности ===
Алгоритм может быть модифицирован для нахождения конкретного набора переменных, на которых тождество не выполняется. Для примера, можно рассмотреть поиск неассоциативной тройки <math display="inline">(a,b,c)</math> за время <math display="inline">O\left(n^2 \log n \log \delta^{-1}\right)</math>. Пусть для некоторых <math>A, B, C \in \Z_2[G]</math> известно, что <math>A \cdot (B \cdot C) \neq (A \cdot B) \cdot C</math>. Данным элементам можно сопоставить тройку <math>A', B', C'</math>, такую что если <math>a_i=0</math>, то <math>a_i'</math> также равно <math>0</math>, а если <math>a_i=1</math>, то <math>a_i'</math> выбирается случайным образом между <math>0</math> и <math>1</math> (аналогично для <math>b_i'</math> и <math>c_i'</math>). Для вероятности того, что <math>A' \cdot (B' \cdot C') \neq (A' \cdot B') \cdot C'</math>, будет всё ещё верна оценка снизу <math display="inline">\frac 1 8</math>, потому процедуру можно повторять до тех пор, пока каждый из элементов <math>A', B', C'</math> не будет иметь единицу лишь в одной из позиций, что будет соответствовать искомой неассоциативной тройке в <math>G</math><ref>{{sfn-текст|Rajagopalan, Schulman|2000|pp=1159—1160}}</ref>.

== Примечания ==
{{примечания}}

== Литература ==
{{refbegin}}
* {{Cite Q|Q108399966|ref=Clifford, Preston}}
* {{Cite Q|Q107209455|ref=Lee, Magniez, Santha}}
* {{Cite Q|Q107209461|ref=Lipton, Regan}}
* {{Cite Q|Q108399209|ref=Matoušek, Nešetřil}}
* {{Cite Q|Q107212518|ref=Premchand}}
* {{Cite Q|Q107209440|ref=Rajagopalan, Schulman}}
* {{Cite Q|Q107219466|ref=Rajagopalan, Schulman}}
* {{Cite Q|Q108368560|ref=Schulman}}
* {{Cite Q|Q108368950|ref=Sinclair}}
* {{Cite Q|Q107923280|ref=Tarjan}}
{{refend}}

{{Хорошая статья|Математика}}

[[Категория:Общая алгебра]]
[[Категория:Бинарные операции]]