complétude de la reconnaissance de la différence de deux permutations

Shor a déclaré, dans son commentaire à la réponse d'un orignal anonyme à cette question Pouvez-vous identifier la somme de deux permutations en temps polynomial? , qu'il est complet d'identifier la différence de deux permutations. Malheureusement, je ne vois pas de réduction directe du problème de somme de permutation et il est utile d'avoir la réduction de la complétude pour le problème de différence de permutation.N $NP$$NP$

Différence de permutation:

INSTANCE: Un tableau d'entiers positifs.$A[1...n]$

QUESTION: Existe-t-il deux permutations et des entiers positifs tels que pour ?σ 1 , 2 , . . . , n | π ( i ) - σ ( i ) | = A [ i ] 1 ≤ i ≤ $\pi$$\sigma$$1,2, ... , n$$|\pi(i) - \sigma(i)| = A[i]$$1 \le i \le n$

Quelle est la réduction pour prouver l' aptitude reconnaître la différence de deux permutations?$NP$

EDIT 10-9-2014 : Le commentaire de Shor donne une réduction qui prouve la complétude lorsque les éléments de la séquence sont des différences signées . Cependant, je ne vois pas de réduction facile à mon problème où tous les éléments de sont les valeurs absolues des différences.$NP$$A$$A$

MISE À JOUR: Le problème de la différence de permutation semble être complet, même si l'une des deux permutations est toujours la permutation d'identité. La preuve de dureté de ce cas spécial est la bienvenue. Donc, je suis intéressé par la complétude de cette version restreinte:N $NP$$NP$

Différence de permutation restreinte: INSTANCE: Un tableau d'entiers positifs.$A[1...n]$

QUESTION: Existe-t-il une permutation des entiers positifs tels que pour ?1 , 2 , . . . , n | π ( i ) - i | = A [ i ] 1 ≤ i ≤ $\pi$$1,2, ... , n$$|\pi(i) - i| = A[i]$$1 \le i \le n$

Mise à jour 2 : le problème restreint est décidable efficacement comme le montre la réponse de mjqxxxx. La complexité de calcul du problème d'origine n'est pas prouvée.

EDIT 9/6/16 : Je suis intéressé à déterminer si cette simplification de la différence de permutation est NP-complète:

Différence de permutation restreinte:

INSTANCE : Un multi-ensemble d'entiers positifs.$A$

QUESTION : Existe-t-il une permutation des entiers positifs tels que ?1 , 2 , . . . , n A = { | π ( i ) - i | : $\pi$$1,2, ... , n$$A= \{|\pi(i) - i| :1 \le i \le n\}$

Le problème restreint, où l' une des permutations est l'identité, est certainement dans . Construire le graphe bipartite où chaque sommet i ∈ V 1 = { 1 , 2 , … , n } est connecté au (x) élément (s) j ∈ V 2 = { 1 , 2 , … , n } de telle sorte que | i - j | = A [ i ] . Alors la permutation souhaitée $\mathsf{P}$$i \in V_1=\{1,2,\ldots,n\}$$j \in V_2=\{1,2,\ldots,n\}$$|i-j|=A[i]$$\sigma$existe si et seulement si le graphe a une correspondance parfaite (c'est-à-dire une correspondance avec arêtes), qui peut être déterminée en temps polynomial.$n$

Voici une variante légèrement intéressante où le problème est facile: au lieu d'un ensemble de base de , autorisez n'importe quel sous-ensemble de { 1 , 2 , 4 , 8 , … } . Le but est toujours de trouver une permutation π pour que A = { | π ( 2 k ) - 2 k | : 2 k ∈ Ω } où $\{1,2,3,\ldots,n\}$$\{1,2,4,8,\ldots\}$$\pi$$A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$$\Omega$est la base. Le principal avantage ici est que le nouvel ensemble au sol oblige chaque élément de à être 2 k 1 - 2 k 2 pour certains k 1 , k 2 , et si k 1 ≠ k 2 , alors k 1 et k 2 sont déterminés par ceci différence. Il s'ensuit que pour chaque différence | 2 k 1 - 2 k 2 | dans A , on peut déduire que π ( 2 $A$$2^{k_1}-2^{k_2}$$k_1,k_2$$k_1\ne k_2$$k_1$$k_2$$|2^{k_1} - 2^{k_2}|$$A$ ouπ(2 k 2 )=2 k 1 (ou les deux).$\pi(2^{k_1}) = 2^{k_2}$$\pi(2^{k_2}) = 2^{k_1}$

Résoudre efficacement cette variation simplifiée est alors plus ou moins routinier. Commencez par construire le multigraphe bipartite non dirigé où L et R sont des copies distinctes de l'ensemble de base, et ajoutez des bords ( 2 k 1 , 2 k 2 ) et ( 2 k 2 , 2 k 1 ) chaque fois | 2 k 1 - 2 k 2 | apparaît dans$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}|$ avec k 1 ≠ k 2 . Je prétends que les éléments suivants sont équivalents:$A$$k_1 \ne k_2$

1. Il y a une permutation avec les différences $\pi$$A$
2. Chaque sommet de a un degré 0 ou 2$G$

Je ne vais pas vraiment le prouver à cause du temps, mais ce n'est pas trop mal de travailler seul. Que est simple. Que$1 \implies 2$ est un peu plus ardu, mais ce n'est pas si mal quand on raisonne avec l'automorphisme de G qui envoie chaque sommet de L à sa copie en R (et vice-versa). La preuve que j'ai en tête dirige les arêtes en G de sorte que toutes les arêtes d'un cycle tournent `` de la même manière autour du cycle '' (chaque sommet non isolé a en degré = hors degré = 1), et de sorte que le précédent l'automorphisme de G reste un automorphisme de la version dirigée. π est alors choisiefonction des bords qui vont de L à R .$2 \implies 1$$G$$L$$R$$G$$G$$\pi$$L$$R$

Vous pouvez formuler l'algorithme ci-dessus comme une question de correspondance parfaite, et j'imagine qu'il existe d'autres réductions de 2-SAT. Je ne vois cependant pas comment étendre ces approches au problème d'origine.