Podzbiór Suma: zredukuj przypadek specjalny do ogólnego

Wikipedia stwierdza problem sumy podzbiorów jako znalezienie podzbioru danego zbioru wielu liczb całkowitych, którego suma wynosi zero. Dalej stwierdza, że jest to równoważne ze znalezieniem podzbioru z sumą $s$ dla dowolnego danego $s$ .

Sądzę więc, że ponieważ są one równoważne, musi nastąpić zmniejszenie po obu stronach. Jeden od $s$ do zera jest trywialny, ustawiając $s = 0$ . Ale nie miałem szczęścia znaleźć redukcji od zera do $s$ , tj. Biorąc pod uwagę zestaw liczb całkowitych $A$ , skonstruuj zestaw liczb całkowitych $B$ zawierający podzbiór z sumą $s$ (dla dowolnych $s$ ), tylko wtedy, gdy istnieje taki podzbiór $A$ z suma zero.

Czy możesz podać mi wskazówki?

complexity-theory reductions np-hard

— ipsec
źródło

Odpowiedzi:

W rzeczywistości masz już redukcję ze specjalnej na ogólną. Ustawiając , zasadniczo używasz ogólnego algorytmu do rozwiązania specjalnego problemu. $s=0$

W drugą stronę (tj. Redukcję z ogólnej do specjalnej):

Załóżmy, że przy danym zestawie a liczba i trzeba sprawdzić, czy nie jest pewnego podzbioru które sumuje się do . $S = \{x_1, \dots, x_n\}$ $K$ $S$ $K$

Teraz chcesz rozwiązać ten problem, biorąc pod uwagę algorytm dla przypadku, w którym możesz określić, czy niektóre podzbiory sumują się do . $0$

Teraz jeśli , mamy łatwą redukcję: . $x_i \gt 0$ $S' = \{x_1, x_2, \dots, x_n, -K\}$

jest podzbiór sumy IFF ma podzbiór sumie . $S'$ $0$ $S$ $K$

Problem występuje, gdy możemy mieć dla niektórych z . $x_i \le 0$ $i$

Możemy założyć, że (dlaczego?). $K \gt 0$

Załóżmy, że suma pozytywnych jest i ujemny to . $x_i$ $P$ $x_i$ $N$

Teraz skonstruuj nowy zestaw taki, że $S' = \{y_1, y_2 \dots, y_n\}$

gdzie . $y_i = x_i + M$ $M = P + |N| + K$

Każdy . $y_i \gt 0$

Teraz uruchom na zestawach algorytm sumy zerowej

$S' \cup \{-(K+M)\}$

$S' \cup \{-(K+2M)\}$

$S' \cup \{-(K+3M)\}$

$\dots$

$S' \cup \{-(K+nM)\}$

Łatwo jest wykazać, że jeśli ma podzbiór sumy , to co najmniej jeden z powyższych zestawów ma podzbiór sumy zero. $S$ $K$

Pozostawiam dowód innego kierunku.

— Aryabhata
źródło

Dziękuję Ci bardzo. Zastanawiam się, czy istnieje redukcja, która przekształca wystąpienie sumy zerowej w jedną (zamiast

) wystąpienie sumy częściowej K?

n

$n$

— ipsec

@ipsec: Masz na myśli przekształcenie wystąpienia sumy K-podzbioru na sumę 0-podzbioru? Być może przyjęcie unii

zestawów powyżej zadziała.

n

$n$

— Aryabhata,

Cóż, właściwie dwa razy zastanawiałem się, czy mam teraz kierunek w prawo. Kiedy chcę pokazać, że suma K podzbioru jest NP-trudna dla każdego K, biorąc pod uwagę fakt, że suma 0-podzbioru jest NP-trudna, mogę zastosować redukcję z sumy 0-podzbioru do sumy K-podzbioru , dla którego potrzebowałbym transformacji wieloczasowej z dowolnej instancji 0 na instancję K. Ale nie jestem teraz pewien, czy tak właśnie zadałem w swoim pytaniu.

— ipsec

s = 0

$s=0$

K

$K$

K

$K$

K

$K$

K

$K$

k

$k$

k

$k$

Nieważne. Zastanawiałem się pierwotnie nad tym, skoro wiemy, że suma zerowa jest NP-trudna, czy możemy wywnioskować, że np. Również suma częściowa? Wikipedia tak mówi, ale szukałem odpowiedniej redukcji. Widzę jednak teraz, że moje sformułowania zostały całkowicie pomieszane i faktycznie pytałem o coś przeciwnego. W każdym razie dałeś mi wystarczająco dużo danych wejściowych, aby zredukować instancję z dowolnej sumy K do instancji sumy L dla dowolnej liczby całkowitej K i L, więc mój problem jest nadal rozwiązany.

— ipsec

$c$ $cK$ $c=2(n+1)$

$(S = \{x_1, \dots, x_n\}, K)$ $K$

$Y = \{y_1, \dots, y_n\}$ $y_i = 2(n+1)x_i + 1$
$z = -2K(n+1)-n$
$n-1$

$K$ $K$ $K$ $K$ $K=0$ wtedy nie musimy w ogóle przekształcać przypadku ogólnego w przypadek specjalny!)

$\{x_{j_1}, \dots, x_{j_m}\}$ $m$ $K$ $y$ $\{y_{j_1}, \dots, y_{j_m}\}$ $2K(n+1)+m$ $-2K(n+1)-n$ $m-n$ $1 \le m \le n$ $[-n+1, 0]$

$2(n+1)$

$\{y_{j'_1}, \dots, y_{j'_{m'}}\}$ $m'$ $Y$ $[1, n-1]$ $z$ $z = -2K(n+1)-n \le -n$ $n-1$

$z$ $Y$ $2(n+1)$ $n$ $Y$ $n-1$ $Y$ $n + n-1 = 2n-1$ $2(n+1)$ $z$ $2(n+1)$ $Y$ $2(n+1)$ $2(n+1)$ $z = -2K(n+1)-n$

$z$

$(-2K(n+1) - n) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}} + 1) + \sum {\text{pull-ups}} = 0$

i możemy zmienić warunki:

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + \sum_{i'=1}^{m'} 1 + \sum {\text{pull-ups}}) = 0$

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)$ $2(n+1)$

$-(n + m' + \sum {\text{pull-ups}}) = 0$

Można to bezpośrednio zastąpić poprzednim równaniem

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) = 0$

$2(n+1)$

$-K + \sum_{i'=1}^{m'} x_{j'_{i'}} = 0$

co daje rozwiązanie pierwotnej instancji problemu ogólnego.

— j_random_hacker
źródło