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 z liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak aby .
Istnieją pewne niezbędne warunki: jeśli są posortowane tak, że , wówczas musimy mieć
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?
Odpowiedzi:
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 problem2 -Numeryczne Dopasowanie z sumami docelowymi:
Wejście: Sekwencja liczb całkowitych dodatnich, Σ n i = 1 do I = n ( n + 1 ) , 1 ≤ i ≤ 2 n dla 1 ≤ í ≤ na1,a2,…an ∑ni=1ai=n(n+1) 1≤ai≤2n 1≤i≤n
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)=ai 1≤i≤n ?
W referencji udowodniono, że mocno ograniczony wariant NUMERYCZNEGO 3-WYMIAROWANEGO DOPASOWANIA (RN3DM) jest silnie NP-kompletny.
Ł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 ≤ n2 ai=e−ui 1≤i≤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.
źródło
Z drugiej strony Marshall Hall wykazał , że można łatwo zidentyfikować różnicę dwóch permutacji.
źródło