Сложность вычисления порядка группы перестановок

10

Учитывая две перестановки и h над n элементами (т.е. членами S n ), какова сложность вычисления порядка подгруппы, сгенерированной g , h ? Или просто решить, имеет ли подгруппа порядок n ! (т. е. все S н )?ghnSng,hn!Sn

Арье
источник

Ответы:

9

В дополнение к ответу Джошуа Грохова:

Вычисление порядка группы перестановок для заданных генераторов производится в P алгоритмом Шрайера – Симса , см. Также с. 8-9 из этих лекций записок Лукса. Как и членство в группах перестановок, многие исследователи полагали, что эта проблема является P-полной, но в итоге было доказано, что она была в NC от Babai, Luks & Seress .

Сложность задач для групп перестановок была тщательно изучена, и их сложность постепенно была решена для абелевых групп, нильпотентных групп, разрешимых групп, групп с ограниченными неабелевыми композиционными факторами и, наконец, групп (см. Работы Бабая, Кука, Ферста, Хопкрофта, Люкса, Маккензи, Малмулей, Сереса и многих других).

Майкл Блондин
источник
Когда Малмулей работал над алгоритмами групп перестановок? (Кроме проблемы Кронекера, которая, возможно, совсем другая вещь ...)
Джошуа Грохов
Возможно, мне не следовало включать его в список, но я имел в виду этот документ: link.springer.com/article/10.1007%2FBF02579205, который позволял получать результаты по группам перестановок, в частности, для этой статьи Cook & McKenzie: epubs.siam .org / doi / abs / 10.1137 / 0216058 .
Михаил Блондин,
Справедливо (похоже, он не знал, что работает над алгоритмом группы перестановок, но Кук-МакКензи показал, что он эквивалентен).
Джошуа Грохов