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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограниченная проблема, где одной из перестановок является тождество, определенно находится в . Построить двудольный граф, в котором каждая вершина связана с элементом (элементами) такими что . Тогда искомая перестановка существует тогда и только тогда, когда граф имеет идеальное совпадение (то есть совпадение с ребрами), которое можно определить за полиномиальное время. i ∈ V 1 = { 1 , 2 , … , n } j ∈ V 2 = { 1 , 2 , … , n } $\mathsf{P}$$i \in V_1=\{1,2,\ldots,n\}$$j \in V_2=\{1,2,\ldots,n\}$σ $|i-j|=A[i]$$\sigma$$n$

Вот слегка интересный вариант, где проблема проста: вместо основного набора , разрешите любое подмножество , Цель по-прежнему найти перестановку так, чтобы где - это базовый набор. Основным преимуществом здесь является то, что новое наземное множество заставляет каждый элемент быть для некоторого , и если , то и определяются этой разницей , Отсюда следует, что для каждой разностив{ 1 , 2 , 4 , 8 , … $\{1,2,3,\ldots,n\}$$\{1,2,4,8,\ldots\}$A = { | π ( 2 к ) - 2 к | : 2 k ∈ Ω } Ω A 2 k 1 - 2 k 2 k 1 , k 2 k 1 ≠ k $\pi$$A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$$\Omega$$A$$2^{k_1}-2^{k_2}$$k_1,k_2$$k_1\ne k_2$k 2 | 2 k 1 - 2 k 2 | A π ( 2 k 1 ) = 2 k 2 π ( 2 k 2 ) = 2 k $k_1$$k_2$$|2^{k_1} - 2^{k_2}|$$A$ , мы можем сделать вывод, что или (или оба).$\pi(2^{k_1}) = 2^{k_2}$$\pi(2^{k_2}) = 2^{k_1}$

Эффективное решение этой упрощенной вариации является более или менее рутинным. Начните с построения неориентированного двудольного мультиграфа где и - отдельные копии основного множества, и добавьте ребра и всякий раз, когда появляется в с . Я утверждаю, что следующее эквивалентно:L R ( 2 k 1 , 2 k 2 ) ( 2 k 2 , 2 k 1 ) | 2 k 1 - 2 k 2 | A k 1 ≠ k $G = (L \sqcup R, E)$$L$$R$$(2^{k_1},2^{k_2})$$(2^{k_2},2^{k_1})$$|2^{k_1} - 2^{k_2}|$$A$$k_1 \ne k_2$

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

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

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