Предположим, что даны таблица умножения конечной группы и некоторая перестановка её элементов. Нужно проверить, является ли эта перестановка автоморфизмом.
По определению, необходимо проверить
где уже дано по условию, что
— биекция. То есть технически для проверки требуется два вложенных цикла, чтобы прогнать это соотношение по всем возможным парам элементов.
Мой вопрос: можно ли это сделать более эффективно?
То есть сделать меньше проверок. Одна очевидная оптимизация заключается в том, что надо проверить, что нейтральный элемент отображается в нейтральный, а из остальных проверок его можно исключить, потому что это будут обычные тождества вида
. Но меня интересует более серьёзная оптимизация. Например, пусть известны (или посчитаны заранее) порождающие элементы данной группы. Их количество будет не более
. Можно ли воспользоваться ими и проверить только верность соотношений только для пар образующая-произвольный элемент? Тогда сложность операции упадёт с
до всего лишь
, что будет вполне достаточно для моих целей. Можно ли будет улучшить это дальше проверяя только пары образующая-образующая?