Сложность задач, связанных с перестановкой

13

Для группы перестановок на и двух векторов где - конечный алфавит, который здесь не совсем уместен, вопрос есть ли какой-нибудь такой, что где означает применение перестановки к ожидаемым образом.G[n]={1,,n}u,vΓnΓπGπ(u)=vπ(u)πu

Предположим далее, что задается в качестве входных данных конечным множеством образующихВ чем сложность проблемы? В частности это в НП?GS

user27313
источник
3
Что вы подразумеваете под конечным набором генераторов? Как это представлено на входе?
РБ
Я думаю, что пример: два генератора , S 2 = ( 1 3 ) ( 2 ) и G - это группа, генерируемая S 1 и S 2 . S1=(12)(3)S2=(13)(2)GS1S2
Maomao
В общем, эта проблема была бы NP-трудной (вероятно, это уже изучалось в некоторых работах, о которых я не знаю). Тем не менее, еще одна проблема решения (также связанная с игрой судоку) может вас заинтересовать
Никос М.
Более того, это обратная проблема (к которой можно подходить МАКСИМАЛЬНО, а-ля Джейнс)
Никос М.
Вопрос не в том, является ли он NP-сложным, а в том, находится ли он в NP. Тривиальная верхняя граница - только PSPACE.
Эмиль Йержабек 3.0

Ответы:

11

Пусть где S n - группа перестановок на n элементах. Тестирование ли г г 1 , ... , г к может быть сделано в NC P по [1]. Пусть u , v Γ n , тогда просто угадайте g S n , проверьте за полиномиальное время, является ли g Gg1,,gk,gSnSnngg1,,gkNCPu,vΓngSngGи является ли . Это дает верхнюю границу NP .g(u)=vNP

Чтобы дополнить этот ответ:

Было показано, что членство в группах принадлежит (Furst et al. 1980), затем NC 3 для абелевых групп (McKenzie & Cook 1987; Mulmuley 1987), NC для нильпотентных групп (Luks & McKenzie 1988), разрешимых групп (Luks & McKenzie 1988), группы с ограниченными неабелевыми композиционными факторами (Luks 1986) и, наконец, все группы (Babai et al. 1987). Сходная классификация сложности принадлежности апериодических моноидов обязана (Beaudry 1988; Beaudry et al. 1992; Kozen 1977), которые показывают, что принадлежность к любому фиксированному разнообразию апериодических моноидов либо в AC 0 , в P , в NP , либо в PSPACEPNC3NCAC0PNPPSPACE (и завершить для этого класса с очень немногими исключениями).

[1] Л. Бабай, Э. М. Лукс и А. Сресс. Группы перестановок в NC. Proc. ежегодный симпозиум ACM по теории вычислений, с. 409-420, 1987.19th

Майкл Блондин
источник
1
Мой ответ был неверным, и я удалил его (подгруппа, которую я обозначил N в моем ответе, была в целом ненормальной). Я думаю, что проблема в P (и, вероятно, также в NC), но у меня нет сейчас доказательств.
Цуёси Ито
Я не понимаю, почему ваш ответ неверен. Перестановка действительно может быть легко построена, тогда членство в группах, где группы представлены в виде списка генераторов, находится в NC от Babai, Luks & Seress 87.π
Michael Blondin
1
Один выбор для π может быть легко построен, но что нам делать, если этот π не принадлежит G? Вероятно, есть способ найти правильный π с самого начала, но сейчас я не вижу, как это сделать.
Цуёси Ито
О, ты прав. Я отредактирую свой ответ обратно к верхней границе NP.
Майкл Блондин
Спасибо за редактирование, и извините за то, что вызвал замешательство из-за моего неправильного ответа.
Цуёси Ито
10

Ваша проблема известна как ( -) строковый G -изоморфизм. Он находится в достаточно узком классе задач вокруг Изоморфизм графов: это по крайней мере , столь же трудно , как GI, и в N PC O A M .ΓGNPcoAM

Сокращение от GI: пусть и пустьGSN- индуцированное действиеSnна пары.N=(n2)GSNSn

протокола: Артур случайнымвыбирает элемент G (я не уверенчто это может быть сделано точно равномерно, но я думаючто известные алгоритмы получить достаточно близко к форме для этого результата) и применяет его и к ц и v . С вероятностью 1/2 он меняет местами u и v , затем представляет их Мерлину и спрашивает, что именно.coAMGuvuv

Джошуа Грохов
источник
1
Комбинируя мой комментарий с ответом Майкла Блондина с вашим ответом, теперь я боюсь, что я случайно решил, что GI находится в P (и, вероятно, также в NC).
Цуёси Ито
-2

Несмотря на мои комментарии, я также добавлю ответ.

В случае, если два заданных вектора известны как перестановки друг друга (и известно, что перестановка находится в данной группе ). Тогда перестановка, которая преобразует v u, может быть найдена за линейное время как таковая:Gvu

  1. Совместите 2 вектора один под другим

  2. Перестановка найдена, начиная с 1-го элемента который превращается в 1-й элемент uvu

  3. Получить позицию элемента на предыдущем шаге (от в v ) и повторить шаг (2), затем это 2-й элемент перестановки и так далее, пока все элементы не пройдены.uv

Если неизвестно, являются ли два вектора положительной перестановкой друг друга (или для более общих случаев, когда может быть несколько преобразований, как, например, игра в судоку), проверьте другую проблему решения, которая в общем случае NP-сложна. Это требует использования некоторых преобразований симметрии (например, перестановок), которые удовлетворяют ограничениям данной задачи, для генерации другого решения задачи при заданном исходном решении.

Кроме того, это часть проблем, известных как Обратные проблемы (а-ля Джейнс)

Никос М.
источник
1
Там нет причин , почему перестановки нашли этот путь должна быть в данной группе . G
Эмиль Йержабек 3.0
@ EmilJeřábek, хм, пропустил эту часть, однако в этой части ответа предполагается, что это так (для иллюстративных примеров линейного алгоритма), мы отредактируем ответ
Никос М.
Проверка существования некоторой перестановки, сопоставляющей с v (а также вычисление такой перестановки), тривиальна: просто посчитайте, сколько раз каждый символ встречается в обоих словах. uv
Эмиль Йержабек 3.0
1
Если не является перестановкой v , то ответом на этот случай является «нет», в противном случае такая перестановка π может быть вычислена в лог-пространстве. Однако, это не решает проблему , как π не может быть в G . Исходя из своих текущих предположений, вы предполагаете, что каждый экземпляр является экземпляром «да», который затем может быть тривиально определен в постоянное время. Я не уверен, как вы ответите на вопрос. uvππG
Майкл Блондин
2
Вы не предоставили доказательств для утверждения, что проблема NP-сложна или что она имеет какое-либо отношение к ASP. Согласно ответу Джошуа Грохова, проблема не является NP-сложной, если только иерархия полиномов не рухнет на второй уровень (если быть точным, AM = coAM).
Эмиль Йержабек 3.0