Для группы перестановок на и двух векторов где - конечный алфавит, который здесь не совсем уместен, вопрос есть ли какой-нибудь такой, что где означает применение перестановки к ожидаемым образом.
Предположим далее, что задается в качестве входных данных конечным множеством образующихВ чем сложность проблемы? В частности это в НП?
Ответы:
Пусть где S n - группа перестановок на n элементах. Тестирование ли г ∈ ⟨ г 1 , ... , г к ⟩ может быть сделано в NC ⊆ P по [1]. Пусть u , v ∈ Γ n , тогда просто угадайте g ∈ S n , проверьте за полиномиальное время, является ли g ∈ Gg1,…,gk,g∈Sn Sn n g∈⟨g1,…,gk⟩ NC⊆P u,v∈Γn g∈Sn g∈G и является ли . Это дает верхнюю границу NP .g(u)=v NP
Чтобы дополнить этот ответ:
[1] Л. Бабай, Э. М. Лукс и А. Сресс. Группы перестановок в NC. Proc. ежегодный симпозиум ACM по теории вычислений, с. 409-420, 1987.19th
источник
Ваша проблема известна как ( -) строковый G -изоморфизм. Он находится в достаточно узком классе задач вокруг Изоморфизм графов: это по крайней мере , столь же трудно , как GI, и в N P ∩ C O A M .Γ G NP∩coAM
Сокращение от GI: пусть и пустьG≤SN- индуцированное действиеSnна пары.N=(n2) G≤SN Sn
протокола: Артур случайнымвыбирает элемент G (я не уверенчто это может быть сделано точно равномерно, но я думаючто известные алгоритмы получить достаточно близко к форме для этого результата) и применяет его и к ц и v . С вероятностью 1/2 он меняет местами u и v , затем представляет их Мерлину и спрашивает, что именно.coAM G u v u v
источник
Несмотря на мои комментарии, я также добавлю ответ.
В случае, если два заданных вектора известны как перестановки друг друга (и известно, что перестановка находится в данной группе ). Тогда перестановка, которая преобразует v → u, может быть найдена за линейное время как таковая:G v→u
Совместите 2 вектора один под другим
Перестановка найдена, начиная с 1-го элемента который превращается в 1-й элемент uv u
Получить позицию элемента на предыдущем шаге (от в v ) и повторить шаг (2), затем это 2-й элемент перестановки и так далее, пока все элементы не пройдены.u v
Если неизвестно, являются ли два вектора положительной перестановкой друг друга (или для более общих случаев, когда может быть несколько преобразований, как, например, игра в судоку), проверьте другую проблему решения, которая в общем случае NP-сложна. Это требует использования некоторых преобразований симметрии (например, перестановок), которые удовлетворяют ограничениям данной задачи, для генерации другого решения задачи при заданном исходном решении.
Кроме того, это часть проблем, известных как Обратные проблемы (а-ля Джейнс)
источник