29

There were two questions 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 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?

Community
  • 1
Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • 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 Jun 22 '13 at 16:41

2 Answers2

20

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. Journal of Scheduling, 7:333–348, 2004

EDIT Oct. 1st: Your problem is called PERMUTATION SUMS. It is listed since 1998 in OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 2
    Thanks for the answer. I've answered one 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 since the answer is given in your reference. – Peter Shor Jun 21 '13 at 11:15
  • 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 Jun 21 '13 at 16:30
  • 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 Dec 22 '13 at 17:34
4

On the other hand, Marshall Hall showed that it is possible to identify the difference of two permutations easily.

anonymous moose
  • 57
  • 1
  • 14
    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 Jun 18 '13 at 13:26
  • 3
    @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 Dec 25 '13 at 18:55
  • 3
    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 Jul 03 '14 at 19:02