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 a1,a2,an z n liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak abyi=1nai=n(n+1).πσ1nai=πi+σi .

Istnieją pewne niezbędne warunki: jeśli są posortowane tak, że , wówczas musimy miećaia1a2an

i=1kaik(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 )πiσii
Mohammad Al-Turkistany

Odpowiedzi:

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, Σ n i = 1 do I = n ( n + 1 ) , 1 i2 n dla 1 í na1,a2,ani=1nai=n(n+1)1ai2n1in

Pytanie: Czy istnieją dwie permutacje i ψ 2 takie, że ψ 1 ( i ) + ψ 2 ( i ) = a i dla 1 i nψ1ψ2ψ1(i)+ψ2(i)=ai1in ?

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 e takich, że n j = 1 u j + n ( n + 1 ) = n e , czy istnieją dwie permutacje λ i μ takie, że u j + λ ( j ) + μ ( j ) = eU={u1,...,un}ej=1nuj+n(n+1)=neλμuj+λ(j)+μ(j)=eDla ?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 do I = e - U i o 1 i n2ai=eui1in

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 Z zarówno suma, jak i różnica są NP-zupełne. nZ
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
ϕππ¯(i)=n+1π(i)ϕ+π{x1,x2,,xn}ϕπ¯{x1(n+1),x2(n+1),,xn(n+1)}{2,2,2,2,2,2}{5,5,5,9,9,9}
Peter Shor