Русская Википедия:Тест ассоциативности

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Мотивация

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

Тест Лайта

В 1961 году Шаблон:Не переведено 5 и Шаблон:Не переведено 5 опубликовали в книге «Алгебраическая теория полугрупп» тест ассоциативности, сообщённый одному из авторов доктором Лайтом в 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>. Лайт обратил внимание, что если <math> G = \langle S \rangle</math>, то есть у <math>G</math> есть порождающее множество <math>S</math>, то проверку достаточно произвести лишь для <math>g \in S</math>.

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

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

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

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

Алгоритм

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

Для проверки ассоциативности выбираются случайные <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>.

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

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

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

В случае <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> операций.

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

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

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

Литература

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