Известны алгоритмы полиномиального времени для нахождения порождающих множеств групп перестановок, что интересно, поскольку мы можем затем представить эти группы кратко, не отказываясь от алгоритмов полиномиального времени для ответа на многие интересные вопросы, связанные с этими группами.
Однако иногда нас может интересовать набор перестановок , который не образует группу, поэтому этот набор будет представлен в виде , где - группа, порожденная набор генераторов а - это набор перестановок, которых нет в , а не просто .R = ⟨ S ⟩ ∖ Т ⟨ S ⟩ С Т Р ⟨ S ⟩
Была ли проделана какая-либо работа по вычислению такого кодирования в форме пары , возможно, с дополнительной естественной целью минимизации?| S | + | T |
источник