Używam równoważnego sformułowania user17410:
Dane wejściowe: wektorów X = { x 1 , … , x m } powyżej { 0 , 1 } n , n jest częścią danych wejściowych
Pytanie: Czy istnieją dwa różne podzbiory A , B ⊆ X takie, że
∑ x ∈ A x = ∑ x ∈ B xnX={x1,…,xm}{0,1}nn
A,B⊆X
∑x∈Ax=∑x∈Bx
Dowód twardości obejmuje wiele pośrednich redukcji, które następują po tym samym „łańcuchu”, który został użyty do udowodnienia twardości standardowego problemu EQUAL SUBSET SUM:
X3C podzbiór SUM ≤ PODZIAŁU ≤ parzyste-nieparzyste PODZIAŁU ≤ EQUAL SUBSET SUM≤≤≤≤
(Nadal go sprawdzam, więc może być źle :)
KROK 1
Następujący problem ( 0-1 VECTOR SUBSET SUM ) jest NP-zupełny: biorąc pod uwagę , x i wektory powyżej { 0 , 1 } n oraz wektor sumy docelowej t , zdecyduj, czy istnieje A ⊆ X taki, że
∑ x ∈ A x = t Dowód : Bezpośrednia redukcja z DOKŁADNEGO POKRYCIA PRZEZ 3-ZESTAWY (X3C): biorąc pod uwagę zestaw n elementów Y = { yX={x1,…,xm}xi{0,1}ntA⊆X
∑x∈Ax=t
n oraz zbiór
C z
M trzy elementy subsets
C = { C 1 , . . . , C m } budujemy odpowiednie ustawienie instancji SUMA WEKTORU 0-1
x i [ j ] = 1 wtedy i tylko wtedy, gdy element
j jest zawarty w
C i ;
t = [ 1 , 1 , . . .1Y={y1,...,yn}CmC={C1,...,Cm}xi[j]=1jCi .
t=[1,1,...1]
KROK 2
Znalezienie dwóch podzbiorów równej sumie wśród m wektorów 0-1 powyżej { 0 , 1 } n , jest równoważne znalezieniu dwóch podzbiorów A , B wektorów o równej sumie z elementem o ograniczonej wielkości x 1 . . . x m gdzie m a x { x i } = O ( ( m n ) k ) dla ustalonego k .A,Bm{0,1}nA,Bx1...xmmax{xi}=O((mn)k)k
Na przykład zestaw wektorów:
x1 2 1 0 1
x2 1 2 3 1
Jest równoważny wektorom 0-1:
x1 1 1 0 1 1 0 0 0 0
1 0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0 0
^ ^
+-- 0 elsewhere
x2 1 1 1 1 0 0 1 0 0
0 1 1 0 0 0 0 1 0
0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 1 1 1
^ ^ ^
+-- 0 elsewhere
AABmn
Zatem następujący problem jest NP-zupełny.
KROK 3
B={x1,…,xm}xi{0,1}nXB1,B2
∑x∈B1x=∑x∈B2x
X={x1,…,xm}tS=∑xiXb′=−t+2Sb′′=t+SB=X∪{b′,b′′}
( ) Załóżmy, że istnieje taki, że ; ustawiamy i ; mamy
⇒A⊆X∑x∈Ax=tB1=A∪{b′}B2=B∖B1=X∖{A}∪{b′′}
∑x∈B1=b′+∑x∈Ax=t−t+S=2S
∑x∈B2=b′′+∑x∈X∖Ax=b′′+S−∑x∈Ax=2S
( ) Załóżmy, że i mają równą sumę. nie mogą należeć do tego samego zestawu (w przeciwnym razie ich suma wynosi i nie może być „zrównoważona” przez elementy w innym zestawie). Załóżmy, że ; mamy:⇐B1B2b′,b′′≥3Sb′=−t+2S∈B1
−t+2S+∑x∈B1∖{b′}x=t+S+∑x∈B2∖{b′′}x
Dlatego musimy mieć a jest prawidłowym rozwiązaniem dla SUMY WEKTOROWEJ 0-1.∑x∈B1∖{b′}x=tB1∖{b′}
Dopuszczamy tylko wektory 0-1 w zbiorze , więc wektory muszą być „reprezentowane w jedności”, jak pokazano w KROKU 2.Bb′,b′′
KROK 3
Problem jest nadal NP-zupełny, jeśli wektory są ponumerowane od a dwa podzbiory muszą mieć taki sam rozmiar i wymagamy, aby zawierał dokładnie jeden z dla (więc, przez ograniczenie równości wielkości, drugi element pary musi być zawarty w ) ( 0-1 WEKTOR NAWET ODDY ).x1,...,x2nX1,X2X1x2i−1,x2i1≤i≤nX2
Dowód:: Zmniejszenie wynosi od 0 do 1 WEKTORA i jest podobne do zmniejszenia z PARTYCJI do EVEN-ODD PARTITION. Jeśli to wektorów powyżej zamień każdy wektor na dwa wektory powyżej :X={x1,...,xm}m{0,1}n{0,1}2n+2m
1 2 n
--------------------
x_i b_1 b_2 ... b_n
becomes:
1 2 ... 2i ... 2m
--------------------------
x'_2i-1 0 0 ... 1 ... 0 b_1 b_2 ... b_n 0 0 ... 0
x'_2i 0 0 ... 1 ... 0 0 0 ... 0 b_1 b_2 ... b_n
Z powodu elementu wektory i nie mogą być zawarte w tym samym podzbiorze; prawidłowe rozwiązanie partycji 0-1 VECTOR EVEN-ODD odpowiada prawidłowemu rozwiązaniu oryginalnej partycji 0-1 VECTOR (wystarczy wybrać elementy 2m + 1..2m + n każdego wektora rozwiązania odrzucając wektory, które zawierają wszystkie zera w tych pozycjach).2ix′2i−1x′2i
KROK 4
PODSUMOWANIE 0-1 WEKTORÓW RÓWNEGO PODSTAWY (problem w pytaniu) jest NP-całkowite: redukcja z 0-1 WEKTORA NAWET ODRZUTU podobna do redukcji z EVEN-ODD PODZIAŁU na PODSTAWA RÓWNEJ PODSTAWY , jak udowodnił Gerhard J. Woeginger , Zhongliang Yu, W sprawie problemu równej sumy częściowej : biorąc pod uwagę uporządkowany zestaw z wektorów powyżej , budujemy ustaw z wektorów na .A={x1,...,x2m}2m{0,1}nY3m{0,1}2m+n
Dla każdego wektora budujemy wektor nad w ten sposób:x2i−1,1≤i≤my2i−1{0,1}2m+n
1 2 ... i i+1 ... m m+1 m+2 ... m+i ... 2m 2m+1 ... 2m+n
------------------------------------------------------
0 0 ... 2 0 ... 0 0 0 1 0 x_{2i-1}
Dla każdego wektora budujemy wektor na w ten sposób:x2i,1≤i≤m−1y2i{0,1}2m+n
1 2 ... i i+1 ... m m+1 m+2 ... m+i ... 2m 2m+1 ... 2m+n
------------------------------------------------------
0 0 ... 0 2 ... 0 0 0 1 0 x_{2i}
element nax2m
1 2 ... ... m m+1 m+2 ... . 2m 2m+1 ... 2m+n
------------------------------------------------------
2 0 ... ... 0 0 0 1 x_{2m}
Na koniec dodajemy elementów pozornych:m
1 2 ... ... m m+1 m+2 ... ... 2m 2m+1 ... 2m+n
------------------------------------------------------
4 0 ... ... 0 0 0 0 0 ... 0
0 4 ... ... 0 0 0 0 0 ... 0
...
0 0 ... ... 4 0 0 0 0 ... 0
Zauważ jeszcze raz, że wektory zawierające wartości mogą być reprezentowane w „jedności” przy użyciu grupy wektorów 0-1, jak pokazano w KROKU 2.>1
Y ma dwa rozłączne podzbiory mają jednakową sumę wtedy i tylko wtedy, gdy ma nieparzystą partycję. Y1,Y2X