Сложность вычисления лексикографически минимального элемента орбиты

9

Учитывая сильные генераторы для группы (GSn,) действуя на нити длины n и элемент s{0,1}nНасколько сложно вычислить лексикографически минимальный элемент G.sорбита s в G?

Сэмюэль Шлезингер
источник
1
Очевидно, что изоморфизм струн в смысле Бабая сводится к этой задаче, так как x,y струны и группа Gмы можем просто найти их минимальные представители орбиты, как указано выше, и напрямую сравнить их, но не ясно, что если изоморфизм струн прост, то из этого следует легкость. Я посмотрю, если в статье Бабая указано, как это сделать.
Сэмюэль Шлезингер
В статье Бабая этот вопрос не рассматривается; на стр. 11 он прямо говорит, что они не занимаются вопросом нормальных форм. Нельзя сказать, что методы не могут быть полезны для нахождения нормальной формы, просто это будет нетривиальным вкладом.
Джошуа
Спасибо @JoshuaGrochow Я не уверен, есть ли у меня опыт использования этих методов, но я посмотрю, что я могу сделать. Это достаточно сложно, даже если это квазиполиномиальное, что для меня больше не так, как я хотел его использовать.
Сэмюэль Шлезингер
Если вы заинтересованы в конкретных решениях этой проблемы, я рекомендую вам взглянуть на публикации Т. Юнтиллы (которого я цитирую в своем ответе), особенно его докторскую диссертацию и его работу по изоморфизму и симметрии графов в целом.
Бозон

Ответы:

5

Эта проблема FPNP-полный, как показано здесь .

Это означает, что лексикографический лидер орбиты построен в детерминистическом полиномиальном времени с доступом к NP-oracle.

Бозон
источник
5

Эта проблема NP-сложная.

Хотя может быть возможно найти некоторую каноническую форму для изоморфизма строк, скажем, в квазиполигональном времени, не расстраивая наши нынешние догадки о том, как выглядит мир сложности, найти лексикографически наименее изоморфную строку сложно с точки зрения NP. Это как раз содержание предложения 3.1 здесь . На самом деле, они показывают, что он остается NP-трудным, даже когдаG является элементарной абелевой 2-группой (= каждый нетривиальный элемент G имеет порядок 2).

Джошуа Грохов
источник