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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Jun 22, 2013 at 16:41

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Jun 21, 2013 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
    Commented Jun 21, 2013 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
    Commented Dec 22, 2013 at 17:34
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 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
    Commented Jun 18, 2013 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
    Commented Dec 25, 2013 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
    Commented Jul 3, 2014 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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