Shor stated, in his comment to anonymous moose's answer to this question [Can you identify the sum of two permutations in polynomial time?][1], 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][2] 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 input permutations is the identity permutation. Hardness proof of this special case is very welcome.

[1]: http://cstheory.stackexchange.com/a/18056/495
[2]: http://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18056#comment62501_18056