Timeline for Can you identify the sum of two permutations in polynomial time?

5 events

when toggle format	what		by	license	comment
Jul 3, 2014 at 19:02	comment	added	Peter Shor		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.
Dec 25, 2013 at 18:55	comment	added	Mohammad Al-Turkistany		@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.
Jun 18, 2013 at 13:31	review	First posts
Jun 20, 2013 at 9:44
Jun 18, 2013 at 13:26	comment	added	Peter Shor		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.
Jun 18, 2013 at 13:13	history	answered	anonymous moose	CC BY-SA 3.0