полнота распознавания разности двух перестановок

21

Шор заявил в своем комментарии к ответу анонимного лося на этот вопрос. Можете ли вы определить сумму двух перестановок за полиномиальное время? То , что он является полным, чтобы определить разницу двух перестановок. К сожалению, я не вижу прямого сокращения от проблемы суммы перестановок, и было бы полезно иметь уменьшение полноты для проблемы разности перестановок.Н ПNPNP

Перестановка Разница:

INSTANCE: массив натуральных чисел.A[1...n]

ВОПРОС: Существуют ли две перестановки и натуральных чисел такие, что для ?сг 1 , 2 , . , , , п | π ( i ) - σ ( i ) | = A [ i ] 1 i nπσ1,2,...,n|π(i)σ(i)|=A[i]1in

Каково сокращение для доказательства полноты распознавания различия двух перестановок?NP

РЕДАКТИРОВАТЬ 10-9-2014 : Комментарий Шора дает сокращение, которое доказывает полноту, когда элементы последовательности являются знаковыми отличиями. Однако я не вижу простого сокращения моей проблемы, когда все элементы являются абсолютными значениями различий.ANPAA

ОБНОВЛЕНИЕ: Проблема разности перестановок кажется полной, даже если одна из двух перестановок всегда является тождественной перестановкой. Доказательство твердости этого особого случая очень приветствуется. Итак, меня интересует полнота этой ограниченной версии:Н ПNPNP

Ограниченная перестановка Разница: INSTANCE: массив натуральных чисел.A[1...n]

ВОПРОС: Существует ли перестановка π натуральных чисел 1,2,...,n такая, что |π(i)i|=A[i] для 1in ?

Обновление 2. Ограниченная проблема эффективно разрешима, как показано в ответе mjqxxxx. Вычислительная сложность исходной задачи не доказана.

РЕДАКТИРОВАНИЕ 9/6/16 : Мне интересно определить, является ли это упрощение разницы перестановок NP-полным:

Ограниченная разница перестановок:

INSTANCE : Мультимножество A натуральных чисел.

ВОПРОС : Существует ли перестановка натуральных чисел такая, что ?1 , 2 , . , , , n A = { | π ( i ) - i | : 1 i n }π1,2,...,nA={|π(i)i|:1in}

Мухаммед Аль-Туркистани
источник
Почему бы не спросить Питера напрямую? @Peter
caozhu
Вы подразумеваете под электронной почтой? Я сделаю это.
Мохаммед Аль-Туркистани
Возможно, я что-то упускаю, но разве эта проблема не может быть представлена ​​как 2-SAT и, таким образом, может быть решена в polytime? Мы можем предположить WLOG, что одна из перестановок является тождеством (я предполагаю, что здесь A [i] вычисляется циклически; должно ли это иметь большое значение?), А затем мы можем представить вторую матрицу . Быть матрицей перестановок - это совокупность предложений двух переменных, утверждающих, что никакие две не лежат в строке или столбце; и затем говорят, что различие в расположении pi (i) от i - это A [i] ИЛИ двух возможных мест, в которых оно может быть.x[i,j]
Noam
@Noam Спасибо за ваш комментарий. Интересная идея. Я не думал об этом. Однако мне не очевидно, приведет ли это к полиномиальному алгоритму времени, тем более что нам дается только абсолютное значение разностей.
Мухаммед Аль-Туркистани
1
Да, кажется, что разница между подсчетом разрыва циклически или по абсолютной величине может иметь значение.
Noam

Ответы:

5

Ограниченная проблема, где одной из перестановок является тождество, определенно находится в . Построить двудольный граф, в котором каждая вершина связана с элементом (элементами) такими что . Тогда искомая перестановка существует тогда и только тогда, когда граф имеет идеальное совпадение (то есть совпадение с ребрами), которое можно определить за полиномиальное время. i V 1 = { 1 , 2 , , n } j V 2 = { 1 , 2 , , n } |PiV1={1,2,,n}jV2={1,2,,n}σ n|ij|=A[i]σn

mjqxxxx
источник
Я могу что-то упустить, но любое идеальное совпадение не сработает. Вы должны доказать существование ограниченного идеального соответствия. Рассмотрим целое число , которое происходит в два раза во входном массиве . Идеальное совпадение, соответствующее перестановке, должно иметь два ребра с абсолютной разностью . Ваш алгоритм НЕ доказывает существование такого ограниченного соответствия. Это то, что делает проблему трудной и, возможно, NP-полной. A kkAk
Мухаммед Аль-Туркистани
2
@ MohammadAl-Turkistany: Я думаю, что если то связаны с узлами с абсолютной разницей . Идеальное совпадение будет включать в себя как минимум одно ребро от и одно ребро от . Я пришел к такому же выводу несколько раз назад, размышляя об исходной проблеме, но следуя другому пути: я увидел, что ограниченную проблему легко сформулировать как формулу 2-SAT (если вы хотите, я могу добавить к ней ответ , но идея mjqxxxx лучше). u i , u jV 1 v i + A [ i ] , v i - A [ i ] , v j + A [ j ] , v j - A [ j ]A[i]=A[j]=kui,ujV1vi+A[i],viA[i],vj+A[j],vjA[j]V2kuiuj
Марцио Де Биаси
@MarzioDeBiasi Почему этот (и ваш) подход не работает для исходной (неограниченной) проблемы?
Мухаммед Аль-Туркистани
@mjqxxx Я вижу, что ваш подход решает ограниченный случай. Почему его нельзя расширить, чтобы эффективно решить исходную проблему?
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany: потому что в исходной задаче элементы первой перестановки ( в ограниченной версии) не являются фиксированными, и, используя тот же подход, вы получите трехсторонний граф (и в моем подходе 2-SAT с предложение ... которое не является предложением 2-CNF). δ i ( n ) ( π i ( n + A [ i ] ) π i ( n - A [ i ] ) )iδi(n)(πi(n+A[i])πi(nA[i]))
Марцио Де Биаси
0

Вот слегка интересный вариант, где проблема проста: вместо основного набора , разрешите любое подмножество , Цель по-прежнему найти перестановку так, чтобы где - это базовый набор. Основным преимуществом здесь является то, что новое наземное множество заставляет каждый элемент быть для некоторого , и если , то и определяются этой разницей , Отсюда следует, что для каждой разностив{ 1 , 2 , 4 , 8 , }{1,2,3,,n}{1,2,4,8,}A = { | π ( 2 к ) - 2 к | : 2 kΩ } Ω A 2 k 1 - 2 k 2 k 1 , k 2 k 1k 2πA={|π(2k)2k|:2kΩ}ΩA2k12k2k1,k2k1k2k 2 | 2 k 1 - 2 k 2 | A π ( 2 k 1 ) = 2 k 2 π ( 2 k 2 ) = 2 k 1k1k2|2k12k2|A , мы можем сделать вывод, что или (или оба).π(2k1)=2k2π(2k2)=2k1

Эффективное решение этой упрощенной вариации является более или менее рутинным. Начните с построения неориентированного двудольного мультиграфа где и - отдельные копии основного множества, и добавьте ребра и всякий раз, когда появляется в с . Я утверждаю, что следующее эквивалентно:L R ( 2 k 1 , 2 k 2 ) ( 2 k 2 , 2 k 1 ) | 2 k 1 - 2 k 2 | A k 1k 2G=(LR,E)LR(2k1,2k2)(2k2,2k1)|2k12k2|Ak1k2

  1. Существует перестановку с разностямиAπA
  2. Каждая вершина в имеет степень 0 или 2G

На самом деле я не докажу это из-за времени, но не так уж плохо работать самостоятельно. То, что , просто. То, что немного труднее, но это не так уж плохо, когда вы рассуждаете об автоморфизме который отправляет каждую вершину в в свою копию в (и наоборот). Доказательство, которое я имею в виду, направляет ребра в так, чтобы все ребра в цикле проходили "одинаковым образом вокруг цикла" (каждая неизолированная вершина имеет in-степень = out-степень = 1), и поэтому предыдущий автоморфизм группы остается автоморфизмом направленной версии. затем выбирается в соответствии с ребрами, идущими от212G L R G G π L R21GLRGGπLк .R

Вы можете сформулировать приведенный выше алгоритм как вопрос с идеальным соответствием, и я предполагаю, что есть и другие сокращения до 2-SAT. Я не понимаю, как распространить эти подходы на исходную проблему.

Эндрю Морган
источник