<p>The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$.  Construct the bipartite graph where each vertex $i \in V_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$.  Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.</p>

CC BY-SA 3.0
2014-12-11T18:49:37.713Z
I may be missing something, but any perfect matching will not work. You must prove the existence of restricted perfect matching. Consider an integer $k$ which occurs twice in input array $A$. The perfect matching that corresponds to the permutation must have two edges with absolute difference $k$. Your algorithm does NOT prove the existence of such restricted matching. This is what make the problem hard and possibly NP-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-11T23:06:50.673Z
@MohammadAl-Turkistany: I think that if $A[i] = A[j] = k$ then $u_i, u_j \in V_1$ are linked to nodes $v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ with absolute differences $k$. The perfect matching will include at least one edge from $u_i$ and one edge from $u_j$. I came to the same conclusion a few times ago while thinking about the original problem, but following another way: I saw that it is easy to formulate the restricted problem as a 2-SAT formula (if you want I can add an answer with it, but mjqxxxx's idea is better).
Marzio De Biasi
CC BY-SA 3.0
2014-12-12T13:37:45.760Z
@MarzioDeBiasi Why this approach (and yours) does not work for the original (unrestricted ) problem?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-12T14:08:56.660Z
@mjqxxx I see that your approach solves the restricted case. Why can not it be extended to efficiently solve the original problem?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-12T14:49:43.150Z
@MohammadAl-Turkistany: because in the original problem the elements of the first permutation (the $i$s in the restricted version) are not fixed, and using the same approach you end up with a tripartite graph (and in my 2-SAT approach with a $\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$ clause ... which is not a 2-CNF clause).
Marzio De Biasi
CC BY-SA 3.0
2014-12-12T14:54:46.867Z
@MarzioDeBiasi Nice. That suggests an NP-completness reduction to the original problem. :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-12T14:59:28.113Z
@Mohammad-Al-Turkistany: ... indeed :-S ... now I'm examining it again ....
Marzio De Biasi
CC BY-SA 3.0
2014-12-11T17:09:04.910Z
2014-12-11T17:09:04.910Z
mjqxxxx
<p>Here's a mildly interesting variation where the problem is easy:
instead of a ground set of $\{1,2,3,\ldots,n\}$,
allow any subset of $\{1,2,4,8,\ldots\}$.
The goal is still to find a permutation $\pi$
so that $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$
where $\Omega$ is the ground set.
The main advantage here is that
the new ground set forces each element of $A$
to be $2^{k_1}-2^{k_2}$ for some $k_1,k_2$,
and if $k_1\ne k_2$,
then $k_1$ and $k_2$ are determined by this difference.
It follows that for each difference $|2^{k_1} - 2^{k_2}|$ in $A$,
we may infer that $\pi(2^{k_1}) = 2^{k_2}$ or $\pi(2^{k_2}) = 2^{k_1}$ (or
both).</p>

<p>Efficiently solving this simplified variation is then more or less routine.
Begin by constructing the undirected bipartite multigraph $G = (L \sqcup R,
E)$ where $L$ and $R$ are distinct copies of the ground set,
and add edges $(2^{k_1},2^{k_2})$ and $(2^{k_2},2^{k_1})$ whenever
$|2^{k_1} - 2^{k_2}|$ appears in $A$ with $k_1 \ne k_2$.
I claim that the following are equivalent:</p>

<ol>
<li>There is a permutation $\pi$ with differences $A$</li>
<li>Every vertex in $G$ has degree 0 or 2</li>
</ol>

<p>I won't actually prove this because of time, but it's not too bad to work out
on one's own. That $1 \implies 2$ is straightforward. That $2 \implies 1$ is a
bit more arduous, but it's not too bad when you reason with the automorphism
of $G$ which sends each vertex in $L$ to its copy in $R$ (and vice-versa).
The proof I have in mind directs the edges in $G$ so that all edges in a cycle
go ``the same way around the cycle''
(each nonisolated vertex has in-degree = out-degree = 1),
and so that the preceding automorphism of $G$ remains an automorphism of the
directed version.
$\pi$ is then chosen according to the edges that go from $L$ to $R$.</p>

<p>You can phrase the above algorithm as a perfect matching question, and I imagine there are other reductions to 2-SAT. I don't see how to extend these approaches to the original problem though.</p>

CC BY-SA 3.0
2016-09-07T15:50:46.117Z
2016-09-07T15:50:46.117Z
Andrew Morgan
<p>Shor stated, in his comment to anonymous moose's answer to this question <a href="https://cstheory.stackexchange.com/a/18056/495">Can you identify the sum of two permutations in polynomial time?</a>, 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. </p>

<p><strong>Permutation Difference:</strong></p>

<p>INSTANCE: An array $A[1...n]$ of positive integers. </p>

<p>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$ ? </p>

<blockquote>
  <p>What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?</p>
</blockquote>

<p><strong>EDIT 10-9-2014</strong>: <a href="https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18056#comment62501_18056">Shor's comment</a> gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are <em>signed</em> differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.</p>

<p><strong>UPDATE:</strong> <s>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:</p>

<p><strong>Restricted Permutation Difference:</strong>
INSTANCE: An array $A[1...n]$ of positive integers. </p>

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

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

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

<p><strong>Restricted Permutation Difference:</strong></p>

<p><strong>INSTANCE</strong>: A multiset $A$ of positive integers. </p>

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

CC BY-SA 3.0
2014-02-21T03:28:37.407Z
Why not ask Peter directly? @Peter
caozhu
CC BY-SA 3.0
2014-02-21T03:32:47.343Z
Do you mean by Email? I will do that.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-23T19:16:07.090Z
I may be missing something but can't this problem be represented as a 2-SAT and thus be solved in polytime?  We can assume WLOG that one of the permutations is the identity (I'm assuming here that A[i] is calculated cyclically; should that matter much?), and then we can represent the second one by a matrix $x[i,j]$.  Being a permutation matrix is a conjunction of the clauses of two variables stating that no two ones lie in a row or in a column; and then saying that the difference is in locations of pi(i) from i is A[i] is the OR of the two possible places it can be in.
Noam
CC BY-SA 3.0
2014-02-23T19:49:09.933Z
@Noam Thank you for your comment. Interesting idea. I did not think of it. However, It is not obvious to me whether it will lead to polynomial time algorithm especially that we are given only the absolute value of the differences.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-23T20:21:15.583Z
@Noam A[i] is the absolute values ($\pi_i - \sigma_i $) between two positive integers. It is not cyclic (not modulo some integer).
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-23T20:45:17.987Z
Yes, it seems that the difference between counting the gap cyclically or in absolute value can matter.
Noam
CC BY-SA 3.0
2014-02-23T20:52:48.357Z
Having signed differences may lead to PTIME algorithm. Glad that the problem got you interested.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-10-09T14:38:21.603Z
A related question is: Suppose $n = 2^k$. Given a sequence $A_1,\ldots,A_n$, determine if there exist permutations $\pi,\sigma$ whose *XOR* is $A_1,\ldots,A_n$.
Yuval Filmus
<cc.complexity-theory><co.combinatorics><np-hardness><permutations>
$NP$-completeness of recognizing the difference of two permutations
Mohammad Al-Turkistany
# $NP$-completeness of recognizing the difference of two permutations

(Asked by: username_0 on 2014-02-17)

Shor stated, in his comment to anonymous moose's answer to this question [Can you identify the sum of two permutations in polynomial time?](https://cstheory.stackexchange.com/a/18056/495), 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](https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18056#comment62501_18056) 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/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\}$ ?

**Tags:** cc.complexity-theory, co.combinatorics, np-hardness, permutations
> **Comments:**
> **username_1**: Why not ask Peter directly? @Peter  
> **username_0**: Do you mean by Email? I will do that.  
> **username_2**: I may be missing something but can't this problem be represented as a 2-SAT and thus be solved in polytime?  We can assume WLOG that one of the permutations is the identity (I'm assuming here that A[i] is calculated cyclically; should that matter much?), and then we can represent the second one by a matrix $x[i,j]$.  Being a permutation matrix is a conjunction of the clauses of two variables stating that no two ones lie in a row or in a column; and then saying that the difference is in locations of pi(i) from i is A[i] is the OR of the two possible places it can be in.  
> **username_0**: @Noam Thank you for your comment. Interesting idea. I did not think of it. However, It is not obvious to me whether it will lead to polynomial time algorithm especially that we are given only the absolute value of the differences.  
> **username_0**: @Noam A[i] is the absolute values ($\pi_i - \sigma_i $) between two positive integers. It is not cyclic (not modulo some integer).  
> **username_2**: Yes, it seems that the difference between counting the gap cyclically or in absolute value can matter.  
> **username_0**: Having signed differences may lead to PTIME algorithm. Glad that the problem got you interested.  
> **username_3**: A related question is: Suppose $n = 2^k$. Given a sequence $A_1,\ldots,A_n$, determine if there exist permutations $\pi,\sigma$ whose *XOR* is $A_1,\ldots,A_n$.  

---

## 2 answers

### Answer by username_4 on 2014-12-11. Score: 6

The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$. Construct the bipartite graph where each vertex $i \in V\_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V\_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$. Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.

> **Comments:**
> **username_0**: I may be missing something, but any perfect matching will not work. You must prove the existence of restricted perfect matching. Consider an integer $k$ which occurs twice in input array $A$. The perfect matching that corresponds to the permutation must have two edges with absolute difference $k$. Your algorithm does NOT prove the existence of such restricted matching. This is what make the problem hard and possibly NP-complete.  
> **username_5**: @MohammadAl-Turkistany: I think that if $A[i] = A[j] = k$ then $u_i, u_j \in V_1$ are linked to nodes $v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ with absolute differences $k$. The perfect matching will include at least one edge from $u_i$ and one edge from $u_j$. I came to the same conclusion a few times ago while thinking about the original problem, but following another way: I saw that it is easy to formulate the restricted problem as a 2-SAT formula (if you want I can add an answer with it, but mjqxxxx's idea is better).  
> **username_0**: @MarzioDeBiasi Why this approach (and yours) does not work for the original (unrestricted ) problem?  
> **username_0**: @mjqxxx I see that your approach solves the restricted case. Why can not it be extended to efficiently solve the original problem?  
> **username_5**: @MohammadAl-Turkistany: because in the original problem the elements of the first permutation (the $i$s in the restricted version) are not fixed, and using the same approach you end up with a tripartite graph (and in my 2-SAT approach with a $\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$ clause ... which is not a 2-CNF clause).  
> **username_0**: @MarzioDeBiasi Nice. That suggests an NP-completness reduction to the original problem. :)  
> **username_5**: @Mohammad-Al-Turkistany: ... indeed :-S ... now I'm examining it again ....  

---

### Answer by username_6 on 2016-09-07. Score: 0

Here's a mildly interesting variation where the problem is easy:
instead of a ground set of $\{1,2,3,\ldots,n\}$,
allow any subset of $\{1,2,4,8,\ldots\}$.
The goal is still to find a permutation $\pi$
so that $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$
where $\Omega$ is the ground set.
The main advantage here is that
the new ground set forces each element of $A$
to be $2^{k\_1}-2^{k\_2}$ for some $k\_1,k\_2$,
and if $k\_1\ne k\_2$,
then $k\_1$ and $k\_2$ are determined by this difference.
It follows that for each difference $|2^{k\_1} - 2^{k\_2}|$ in $A$,
we may infer that $\pi(2^{k\_1}) = 2^{k\_2}$ or $\pi(2^{k\_2}) = 2^{k\_1}$ (or
both).

Efficiently solving this simplified variation is then more or less routine.
Begin by constructing the undirected bipartite multigraph $G = (L \sqcup R,
E)$ where $L$ and $R$ are distinct copies of the ground set,
and add edges $(2^{k\_1},2^{k\_2})$ and $(2^{k\_2},2^{k\_1})$ whenever
$|2^{k\_1} - 2^{k\_2}|$ appears in $A$ with $k\_1 \ne k\_2$.
I claim that the following are equivalent:

1. There is a permutation $\pi$ with differences $A$
2. Every vertex in $G$ has degree 0 or 2

I won't actually prove this because of time, but it's not too bad to work out
on one's own. That $1 \implies 2$ is straightforward. That $2 \implies 1$ is a
bit more arduous, but it's not too bad when you reason with the automorphism
of $G$ which sends each vertex in $L$ to its copy in $R$ (and vice-versa).
The proof I have in mind directs the edges in $G$ so that all edges in a cycle
go ``the same way around the cycle''
(each nonisolated vertex has in-degree = out-degree = 1),
and so that the preceding automorphism of $G$ remains an automorphism of the
directed version.
$\pi$ is then chosen according to the edges that go from $L$ to $R$.

You can phrase the above algorithm as a perfect matching question, and I imagine there are other reductions to 2-SAT. I don't see how to extend these approaches to the original problem though.


---

