29
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$) $\endgroup$ – Mohammad Al-Turkistany Jun 22 '13 at 16:41
20
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Jun 21 '13 at 11:15
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Jun 21 '13 at 16:30
  • $\begingroup$ 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]? $\endgroup$ – Mohammad Al-Turkistany Dec 22 '13 at 17:34
4
$\begingroup$

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

$\endgroup$
  • 14
    $\begingroup$ 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. $\endgroup$ – Peter Shor Jun 18 '13 at 13:26
  • 3
    $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Dec 25 '13 at 18:55
  • 3
    $\begingroup$ 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. $\endgroup$ – Peter Shor Jul 3 '14 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.