<p>On the other hand, Marshall Hall <a href="http://www.ams.org/journals/proc/1952-003-04/S0002-9939-1952-0050579-7/S0002-9939-1952-0050579-7.pdf" rel="nofollow">showed</a> that it is possible to identify the <em>difference</em> of two permutations easily.</p>

CC BY-SA 3.0
2013-06-18T13:26:47.243Z
Marshall Hall's theorem applies to the sum as well, but both the difference and the sum have to be computed modulo $n$ for his result to apply. Over $\mathbb{Z}$, both the sum and the difference are NP-complete.
Peter Shor 
CC BY-SA 3.0
2013-12-25T18:55:17.467Z
@PeterShor For completeness, please post your comment as separate answer by providing a proof sketch of the NP-completeness of identifying the difference of two permutations.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-03T19:02:20.233Z
For completeness: Suppose we have two permutations $\phi$ and $\pi$. We then have $\bar{\pi}(i) = n+1 - \pi(i)$ is also a permutation. Now, if $\phi+\pi$ is the multiset $\{x_1, x_2, \ldots, x_n\}$, then $\phi-\bar{\pi}$ is the multiset $\{x_1-(n+1), x_2-(n+1), \ldots, x_n-(n+1)\}$. For example, $\{-2,-2,-2,2,2,2\}$ cannot be represented as a difference of two permutations because $\{5,5,5,9,9,9\}$ is not the sum of two permutations.
Peter Shor 
CC BY-SA 3.0
2013-06-18T13:13:56.577Z
2013-06-18T13:13:56.577Z
anonymous moose
<p>No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:</p>

<p>Input: Sequence of $a_1, a_2, \ldots a_n$ of positive integers, $\sum_{i=1}^n a_i = n(n+1)$, $1 \le a_i \le 2n$ for $1 \le i \le n$</p>

<p>Question: Are there two permutations $\psi_1$ and $\psi_2$ such that $\psi_1(i)+\psi_2(i)= a_i$ for $1\le i \le n$?</p>

<p>In the reference, a severely restricted variant of NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) was proven to be strongly NP-complete.</p>

<blockquote>
  <p>RN3DM, Given a multiset $U = \{u_1, . . . , u_n\}$ of integers and an integer $e$ such that $\sum_{j=1}^n  u_j +
n(n + 1) = ne$ , do there exist two permutations $\lambda$ and $\mu$ such that
  $u_j + \lambda( j ) + \mu( j ) = e$, for $j = 1, . . . , n$?</p>
</blockquote>

<p>There is an easy reduction from RN3DM to $2$-Numerical Matching with target sums problem:
Given an instance of RN3DM. We construct the corresponding instance by making $a_i= e-u_i$ for $1 \le i \le n$</p>

<p>W. Yu, H. Hoogeveen, and J. K. Lenstra.
<a href="http://link.springer.com/article/10.1023%2FB%3AJOSH.0000036858.59787.c2" rel="nofollow">Minimizing makespan in a two-machine flow shop with
delays and unit-time operations is NP-hard</a>. Journal of
Scheduling, 7:333–348, 2004</p>

<p><strong>EDIT Oct. 1st</strong>: Your problem is called PERMUTATION SUMS. It is listed since 1998 in <a href="http://people.cs.clemson.edu/~hedet/algorithms.html" rel="nofollow">OPEN PROBLEMS</a> IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.</p>

CC BY-SA 3.0
2013-06-21T11:15:46.207Z
Thanks for the answer. I've answered [one](http://cs.stackexchange.com/questions/12359/2k-number-assignment) of the problems on cs.se which inspired this one (which wasn't in a form answered directly by your reference), but I think you should have the first chance to answer the [second one](http://cs.stackexchange.com/questions/10869/job-scheduling-with-a-bottleneck-problem/10872#comment22604_10872) since the answer is given in your reference.
Peter Shor 
CC BY-SA 3.0
2013-06-21T16:30:02.883Z
Thanks a lot Peter. I am glad that  I was able to help you. I think you will produce a better answer. So, please go ahead and answer that question too.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-22T17:34:56.770Z
Here is the problem statement as it appeared on the above Web page: PERMUTATION SUMS [Cheston, 198X]
INSTANCE: An array A[1..n] of positive integers.
QUESTION: Do there exist two permutations r and s of the positive integers {1,2, ... , n} such that for 1 <= i <= n, r(i) + s(i) = A[i]?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-17T10:29:52.153Z
2016-06-03T15:12:12.653Z
2016-06-03T15:12:12.653Z
Mohammad Al-Turkistany
<p>There were <a href="https://cs.stackexchange.com/questions/10869/job-scheduling-with-a-bottleneck-problem/10872#comment22604_10872">two</a> <a href="https://cs.stackexchange.com/questions/12359/2k-number-assignment">questions</a> asked recently on cs.se which were either related to or had a special case equivalent to the following question:</p>

<p>Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ numbers such that $\sum_{i=1}^n a_i = n(n+1).$  Decompose it into the sum of two permutations, $\pi$ and $\sigma$, of $1 \dots n$, so that $a_i = \pi_i + \sigma_i\,$.</p>

<p>There are some necessary conditions: if the $a_i$  are sorted so that $a_1 \leq a_2 \leq \ldots \leq a_n\,$, then we must have</p>

<p>$$\sum_{i=1}^k a_i \geq k(k+1).$$</p>

<p>However, these conditions are not sufficient. From the answer to <a href="https://math.stackexchange.com/questions/406586/characterizing-multisets-that-are-the-sum-of-two-permutations">this math.se question</a> I asked, the sequence 5,5,5,9,9,9 cannot be decomposed as the sum of two permutations (one can see this by using the fact that both 1 or 5 can only be paired with 4). </p>

<p>So my question is: what is the complexity of this problem?</p>

CC BY-SA 3.0
2013-06-22T16:41:41.997Z
BTW, A simple variation came up to my mind and I am not sure about its complexity. Can you identify the fixed-point free sum of two permutations in polynomial time? (We require that the two permutations disagree at each position i.e. $\pi_i \ne \sigma_i$ for all $i$)
Mohammad Al-Turkistany
<cc.complexity-theory><ds.algorithms><co.combinatorics><np-hardness><permutations>
Can you identify the sum of two permutations in polynomial time?
Peter Shor 
# Can you identify the sum of two permutations in polynomial time?

(Asked by: username_0 on 2013-06-16)

There were [two](https://cs.stackexchange.com/questions/10869/job-scheduling-with-a-bottleneck-problem/10872#comment22604_10872) [questions](https://cs.stackexchange.com/questions/12359/2k-number-assignment) asked recently on cs.se which were either related to or had a special case equivalent to the following question:

Suppose you have a sequence $a\_1, a\_2, \ldots a\_n$ of $n$ numbers such that $\sum\_{i=1}^n a\_i = n(n+1).$ Decompose it into the sum of two permutations, $\pi$ and $\sigma$, of $1 \dots n$, so that $a\_i = \pi\_i + \sigma\_i\,$.

There are some necessary conditions: if the $a\_i$ are sorted so that $a\_1 \leq a\_2 \leq \ldots \leq a\_n\,$, then we must have

$$\sum\_{i=1}^k a\_i \geq k(k+1).$$

However, these conditions are not sufficient. From the answer to [this math.se question](https://math.stackexchange.com/questions/406586/characterizing-multisets-that-are-the-sum-of-two-permutations) I asked, the sequence 5,5,5,9,9,9 cannot be decomposed as the sum of two permutations (one can see this by using the fact that both 1 or 5 can only be paired with 4).

So my question is: what is the complexity of this problem?

**Tags:** cc.complexity-theory, ds.algorithms, co.combinatorics, np-hardness, permutations

> **Comments:**
> **username_1**: BTW, A simple variation came up to my mind and I am not sure about its complexity. Can you identify the fixed-point free sum of two permutations in polynomial time? (We require that the two permutations disagree at each position i.e. $\pi_i \ne \sigma_i$ for all $i$)  

---

## 2 answers

### Answer by username_1 on 2013-06-17. Score: 20 | Accepted answer

No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:

Input: Sequence of $a\_1, a\_2, \ldots a\_n$ of positive integers, $\sum\_{i=1}^n a\_i = n(n+1)$, $1 \le a\_i \le 2n$ for $1 \le i \le n$

Question: Are there two permutations $\psi\_1$ and $\psi\_2$ such that $\psi\_1(i)+\psi\_2(i)= a\_i$ for $1\le i \le n$?

In the reference, a severely restricted variant of NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) was proven to be strongly NP-complete.

> RN3DM, Given a multiset $U = \{u\_1, . . . , u\_n\}$ of integers and an integer $e$ such that $\sum\_{j=1}^n u\_j +
> n(n + 1) = ne$ , do there exist two permutations $\lambda$ and $\mu$ such that
> $u\_j + \lambda( j ) + \mu( j ) = e$, for $j = 1, . . . , n$?

There is an easy reduction from RN3DM to $2$-Numerical Matching with target sums problem:
Given an instance of RN3DM. We construct the corresponding instance by making $a\_i= e-u\_i$ for $1 \le i \le n$

W. Yu, H. Hoogeveen, and J. K. Lenstra.
[Minimizing makespan in a two-machine flow shop with
delays and unit-time operations is NP-hard](http://link.springer.com/article/10.1023%2FB%3AJOSH.0000036858.59787.c2). Journal of
Scheduling, 7:333–348, 2004

**EDIT Oct. 1st**: Your problem is called PERMUTATION SUMS. It is listed since 1998 in [OPEN PROBLEMS](http://people.cs.clemson.edu/~hedet/algorithms.html) IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.

> **Comments:**
> **username_0**: Thanks for the answer. I've answered [one](http://cs.stackexchange.com/questions/12359/2k-number-assignment) of the problems on cs.se which inspired this one (which wasn't in a form answered directly by your reference), but I think you should have the first chance to answer the [second one](http://cs.stackexchange.com/questions/10869/job-scheduling-with-a-bottleneck-problem/10872#comment22604_10872) since the answer is given in your reference.  
> **username_1**: Thanks a lot Peter. I am glad that  I was able to help you. I think you will produce a better answer. So, please go ahead and answer that question too.  
> **username_1**: Here is the problem statement as it appeared on the above Web page: PERMUTATION SUMS [Cheston, 198X] INSTANCE: An array A[1..n] of positive integers. QUESTION: Do there exist two permutations r and s of the positive integers {1,2, ... , n} such that for 1 <= i <= n, r(i) + s(i) = A[i]?  

---

### Answer by username_2 on 2013-06-18. Score: 4

On the other hand, Marshall Hall [showed](http://www.ams.org/journals/proc/1952-003-04/S0002-9939-1952-0050579-7/S0002-9939-1952-0050579-7.pdf) that it is possible to identify the *difference* of two permutations easily.

> **Comments:**
> **username_0**: Marshall Hall's theorem applies to the sum as well, but both the difference and the sum have to be computed modulo $n$ for his result to apply. Over $\mathbb{Z}$, both the sum and the difference are NP-complete.  
> **username_1**: @PeterShor For completeness, please post your comment as separate answer by providing a proof sketch of the NP-completeness of identifying the difference of two permutations.  
> **username_0**: For completeness: Suppose we have two permutations $\phi$ and $\pi$. We then have $\bar{\pi}(i) = n+1 - \pi(i)$ is also a permutation. Now, if $\phi+\pi$ is the multiset $\{x_1, x_2, \ldots, x_n\}$, then $\phi-\bar{\pi}$ is the multiset $\{x_1-(n+1), x_2-(n+1), \ldots, x_n-(n+1)\}$. For example, $\{-2,-2,-2,2,2,2\}$ cannot be represented as a difference of two permutations because $\{5,5,5,9,9,9\}$ is not the sum of two permutations.  

---

