Тест ассоциативности
Материал из Википедии — свободной encyclopedia
Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует времени, где — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за , если исследуемая бинарная операция обратима (задаёт квазигруппу). Первый вероятностный тест, улучшающий время работы с до , был предложен в 1996 году Шридхаром Раджагопаланом и Леонардом Шульманом[англ.]. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время , что является улучшением по сравнению с поиском Гровера, работающим за [1].