Учитывая сильные генераторы для группы действуя на нити длины и элемент Насколько сложно вычислить лексикографически минимальный элемент орбита в ?
permutations
gr.group-theory
complexity
Сэмюэль Шлезингер
источник
источник
Ответы:
Эта проблемаFPNP -полный, как показано здесь .
Это означает, что лексикографический лидер орбиты построен в детерминистическом полиномиальном времени с доступом кNP -oracle.
источник
Эта проблема NP-сложная.
Хотя может быть возможно найти некоторую каноническую форму для изоморфизма строк, скажем, в квазиполигональном времени, не расстраивая наши нынешние догадки о том, как выглядит мир сложности, найти лексикографически наименее изоморфную строку сложно с точки зрения NP. Это как раз содержание предложения 3.1 здесь . На самом деле, они показывают, что он остается NP-трудным, даже когдаG является элементарной абелевой 2-группой (= каждый нетривиальный элемент G имеет порядок 2).
источник