Pouvez-vous identifier la somme de deux permutations en temps polynomial?

29

Il y avait deux questions posées récemment sur cs.se qui étaient liées ou avaient un cas spécial équivalent à la question suivante:

Supposons que vous ayez une séquence de n nombres tels que n i = 1 a i = n ( n + 1 ) . Décomposer en la somme de deux permutations, π et σ , de 1 n , de sorte que a i = π i + σ ia1,a2,anni=1nai=n(n+1).πσ1nai=πi+σi.

Il y a quelques conditions nécessaires: si les sont triés de telle sorte que a 1a 2a naia1a2an, alors nous devons avoir

i=1kaik(k+1).

Cependant, ces conditions ne sont pas suffisantes. D'après la réponse à cette question math.se que j'ai posée, la séquence 5,5,5,9,9,9 ne peut pas être décomposée comme la somme de deux permutations (on peut le voir en utilisant le fait que 1 ou 5 ne peuvent être jumelé avec 4).

Ma question est donc: quelle est la complexité de ce problème?

Peter Shor
la source
BTW, Une simple variation m'est venue à l'esprit et je ne suis pas sûr de sa complexité. Pouvez-vous identifier la somme libre en virgule fixe de deux permutations en temps polynomial? (Nous exigeons que les deux permutations soient en désaccord à chaque position, c'est-à-dire pour tout i )πiσii
Mohammad Al-Turkistany

Réponses:

20

Non, vous ne pouvez pas identifier la somme de deux permutations en temps polynomial à moins que P = NP. Votre problème est NP-complet car la version de décision de votre problème est équivalente au problème NP-complete - Correspondance numérique avec les sommes cibles:2

Entrée: Séquence d' des nombres entiers positifs, Σ n i = 1 à i = n ( n + 1 ) , 1 a i2 n pour 1 i na1,a2,ani=1nai=n(n+1)1ai2n1in

Question: Y a-t-il deux permutations et ψ 2 telles que ψ 1 ( i ) + ψ 2 ( i ) = a i pour 1 i n ?ψ1ψ2ψ1(i)+ψ2(i)=ai1in

Dans la référence, une variante fortement restreinte de CORRESPONDANCE NUMÉRIQUE EN 3 DIMENSIONS (RN3DM) s'est avérée être fortement NP-complète.

RN3DM, étant donné un multiset d'entiers et un entier e tel que n j = 1 u j + n ( n + 1 ) = n e , existe-t-il deux permutations λ et μ telles que u j + λ ( j ) + μ ( j ) = eU={u1,...,un}ej=1nuj+n(n+1)=neλμuj+λ(j)+μ(j)=e, Pour ?j=1,...,n

Il y a une réduction facile de RN3DM à Problème de correspondance numérique avec les sommes cibles: étant donné une instance de RN3DM. Nous construisons l'instance correspondante en faisant a i = e - u i pour 1 i n2ai=eui1in

W. Yu, H. Hoogeveen et JK Lenstra. Réduire au minimum la durée de vie dans un atelier de flux à deux machines avec des retards et des opérations à l'unité est NP-difficile . Journal of Scheduling, 7: 333–348, 2004

EDIT 1er octobre : votre problème s'appelle SOMMES DE PERMUTATION. Il est répertorié depuis 1998 dans OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION de Steve Hedetniemi.

Mohammad Al-Turkistany
la source
2
Merci d'avoir répondu. J'ai répondu à l' un des problèmes sur cs.se qui a inspiré celui-ci (qui n'a pas été répondu directement par votre référence), mais je pense que vous devriez avoir la première chance de répondre au second puisque la réponse est donnée dans votre référence.
Peter Shor
Merci beaucoup Peter. Je suis content d'avoir pu vous aider. Je pense que vous produirez une meilleure réponse. Alors, allez-y et répondez également à cette question.
Mohammad Al-Turkistany
Voici l'énoncé du problème tel qu'il apparaît sur la page Web ci-dessus: SOMMES DE PERMUTATION [Cheston, 198X] INSTANCE: Un tableau A [1..n] d'entiers positifs. QUESTION: Existe-t-il deux permutations r et s des entiers positifs {1,2, ..., n} telles que pour 1 <= i <= n, r (i) + s (i) = A [i] ?
Mohammad Al-Turkistany
4

En revanche, Marshall Hall a montré qu'il est possible d'identifier facilement la différence de deux permutations.

orignal anonyme
la source
14
Le théorème de Marshall Hall s'applique également à la somme, mais la différence et la somme doivent être calculées modulo pour que son résultat s'applique. Sur Z , la somme et la différence sont NP-complètes. nZ
Peter Shor
3
@PeterShor Pour l'exhaustivité, veuillez poster votre commentaire comme réponse distincte en fournissant un croquis de preuve de l'exhaustivité NP de l'identification de la différence de deux permutations.
Mohammad Al-Turkistany
3
Pour être complet: Supposons que nous ayons deux permutations et π . On a alors ˉ π ( i ) = n + 1 - π ( i ) est aussi une permutation. Maintenant, si ϕ + π est le multiset { x 1 , x 2 , , x n } , alors ϕ - ˉ π est le multiset { x 1 - ( n + 1 )ϕππ¯(i)=n+1π(i)ϕ+π{x1,x2,,xn}ϕπ¯{x1(n+1),x2(n+1),,xn(n+1)}{2,2,2,2,2,2}{5,5,5,9,9,9}
Peter Shor