Skip to main content
8 of 12
added 162 characters in body

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a straightforward reduction from the permutation sum problem and it is useful to have the $NP$-completeness reduction for the permutation difference problem.

Permutation Difference:

INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Do there exist two permutations $\pi$ and $\sigma$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - \sigma(i)| = A[i]$ for $1 \le i \le n$ ?

What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?

EDIT 10-9-2014: Shor's comment gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are signed differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.

UPDATE: The Permutation Difference problem seems to be $NP$-complete even if one of the two permutations is always the identity permutation. Hardness proof of this special case is very welcome. So, I am interested in $NP$-completeness of this restricted version:

Restricted Permutation Difference: INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - i| = A[i]$ for $1 \le i \le n$ ?

Update 2: The restricted problem is efficiently decidable as shown by mjqxxxx's answer. The computational complexity of the original problem is not proven.