Учитывая две перестановки и h над n элементами (т.е. членами S n ), какова сложность вычисления порядка подгруппы, сгенерированной g , h ? Или просто решить, имеет ли подгруппа порядок n ! (т. е. все S н )?
10
Учитывая две перестановки и h над n элементами (т.е. членами S n ), какова сложность вычисления порядка подгруппы, сгенерированной g , h ? Или просто решить, имеет ли подгруппа порядок n ! (т. е. все S н )?
В дополнение к ответу Джошуа Грохова:
Вычисление порядка группы перестановок для заданных генераторов производится в P алгоритмом Шрайера – Симса , см. Также с. 8-9 из этих лекций записок Лукса. Как и членство в группах перестановок, многие исследователи полагали, что эта проблема является P-полной, но в итоге было доказано, что она была в NC от Babai, Luks & Seress .
Сложность задач для групп перестановок была тщательно изучена, и их сложность постепенно была решена для абелевых групп, нильпотентных групп, разрешимых групп, групп с ограниченными неабелевыми композиционными факторами и, наконец, групп (см. Работы Бабая, Кука, Ферста, Хопкрофта, Люкса, Маккензи, Малмулей, Сереса и многих других).
источник