Return to Question

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:

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.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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

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:

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.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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

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:

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.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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

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:

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.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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

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.

EDIT 9/23/15: I am looking for NP-completeness proof for this problem:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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

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:

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.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

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