Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym?

29

Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem:

Załóżmy, że masz ciąg $a_1, a_2, \ldots a_n$ z $n$ liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby $\sum_{i=1}^n a_i = n(n+1).$ $\pi$ $\sigma$ $1 \dots n$ $a_i = \pi_i + \sigma_i\,$ .

Istnieją pewne niezbędne warunki: jeśli są posortowane tak, że , wówczas musimy mieć $a_i$ $a_1 \leq a_2 \leq \ldots \leq a_n\,$

\sum_{i = 1}^{k} a_{i} \geq k (k + 1) .

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

Te warunki nie są jednak wystarczające. Od odpowiedzi na to pytanie matematyczne mnie pytanie matematyczne. Sekwencji 5,5,5,9,9,9 nie można rozłożyć na sumę dwóch permutacji (można to zobaczyć, wykorzystując fakt, że zarówno 1, jak i 5 mogą tylko sparować z 4).

Moje pytanie brzmi: jaka jest złożoność tego problemu?

— Peter Shor
źródło

BTW, Przyszła mi do głowy prosta odmiana i nie jestem pewien jej złożoności. Czy potrafisz zidentyfikować stałą sumę swobodną dwóch permutacji w czasie wielomianowym? (Wymagamy, aby dwie permutacje nie zgadzały się w każdej pozycji, tj.

dla wszystkich

)

π_{i} \neq σ_{i}

$\pi_i \ne \sigma_i$

i

$i$

— Mohammad Al-Turkistany

20

Nie, nie można zidentyfikować sumy dwóch permutacji w czasie wielomianowym, chyba że P = NP. Twój problem jest NP-kompletny, ponieważ wersja decyzyjna twojego problemu jest równoważna z NP-complete problem $2$ -Numeryczne Dopasowanie z sumami docelowymi:

Wejście: Sekwencja liczb całkowitych dodatnich, , dla $a_1, a_2, \ldots a_n$ $\sum_{i=1}^n a_i = n(n+1)$ $1 \le a_i \le 2n$ $1 \le i \le n$

Pytanie: Czy istnieją dwie permutacje i takie, że dla $\psi_1$ $\psi_2$ $\psi_1(i)+\psi_2(i)= a_i$ $1\le i \le n$ ?

W referencji udowodniono, że mocno ograniczony wariant NUMERYCZNEGO 3-WYMIAROWANEGO DOPASOWANIA (RN3DM) jest silnie NP-kompletny.

RN3DM, daną multiset liczb całkowitych i liczb całkowitych takich, że , czy istnieją dwie permutacje i takie, że $U = \{u_1, . . . , u_n\}$ $e$ $\sum_{j=1}^n u_j + n(n + 1) = ne$ $\lambda$ $\mu$ $u_j + \lambda( j ) + \mu( j ) = e$ Dla ? $j = 1, . . . , n$

Łatwo jest zredukować problem z RN3DM do numerycznego dopasowania z docelowymi sumami: Biorąc pod uwagę instancję RN3DM. Skonstruować odpowiednie wystąpienie poprzez o $2$ $a_i= e-u_i$ $1 \le i \le n$

W. Yu, H. Hoogeveen i JK Lenstra. Minimalizowanie makespan w sklepie z dwiema maszynami z opóźnieniami i operacjami jednostkowymi jest trudne . Journal of Scheduling, 7: 333–348, 2004

EDYCJA 1 października : Twój problem nosi nazwę PERMUTATION SUMS. Jest wymieniony od 1998 roku w OTWARTYCH PROBLEMACH W OPTYMALIZACJI KOMBINATOROWEJ Steve'a Hedetniemi.

— Mohammad Al-Turkistany
źródło

2

Dziękuję za odpowiedź. Odpowiedziałem na jeden z problemów na cs.se, który zainspirował ten (który nie był w formie odpowiedzi bezpośrednio przez twoje odniesienie), ale myślę, że powinieneś mieć pierwszą szansę, aby odpowiedzieć na drugi, ponieważ odpowiedź jest podana w twojej referencji.

— Peter Shor,

Wielkie dzięki Peter. Cieszę się, że mogłem ci pomóc. Myślę, że udzielisz lepszej odpowiedzi. Więc proszę, odpowiedz także na to pytanie.

— Mohammad Al-Turkistany

Oto opis problemu, jaki pojawił się na powyższej stronie internetowej: SUMSY UPRAWNIANIA [Cheston, 198X] INSTANCJA: Tablica A [1..n] dodatnich liczb całkowitych. PYTANIE: Czy istnieją dwie permutacje r i s dodatnich liczb całkowitych {1,2, ..., n} takie, że dla 1 <= i <= n, r (i) + s (i) = A [i] ?

— Mohammad Al-Turkistany

4

Z drugiej strony Marshall Hall wykazał , że można łatwo zidentyfikować różnicę dwóch permutacji.

— anonimowy łoś
źródło

14

Marshall Hall to twierdzenie ma zastosowanie do sumy, a także, ale zarówno różnica i suma muszą być obliczane modulo

na jego wynik do zastosowania. Powyżej

zarówno suma, jak i różnica są NP-zupełne.

n

$n$

Z

$\mathbb{Z}$

— Peter Shor,

3

@PeterShor Aby uzyskać kompletność, proszę zamieścić komentarz jako osobną odpowiedź, przedstawiając szkic dowodu kompletności NP identyfikującej różnicę dwóch permutacji.

— Mohammad Al-Turkistany,

3

ϕ

$\phi$

π

$\pi$

\bar{π} (i) = n + 1 - π (i)

$\bar{\pi}(i) = n+1 - \pi(i)$

ϕ + π

$\phi+\pi$

{x_{1}, x_{2}, \dots, x_{n}}

$\{x_1, x_2, \ldots, x_n\}$

ϕ - \bar{π}

$\phi-\bar{\pi}$

{x_{1} - (n + 1), x_{2} - (n + 1), \dots, x_{n} - (n + 1)}

$\{x_1-(n+1), x_2-(n+1), \ldots, x_n-(n+1)\}$

{- 2, - 2, - 2, 2, 2, 2}

$\{-2,-2,-2,2,2,2\}$

{5, 5, 5, 9, 9, 9}

$\{5,5,5,9,9,9\}$

— Peter Shor