Jak mogę zmniejszyć sumę podzbiorów do partycji?

21

Może to dość proste, ale mam problem z uzyskaniem tej redukcji. Chcę zredukować sumę podzbioru do partycji, ale w tej chwili nie widzę relacji!

Czy można zmniejszyć ten problem za pomocą funkcji redukcji Levina?

Jeśli nie rozumiesz, napisz o wyjaśnienia!

complexity-theory np-complete reductions

— dbonadiman
źródło

19

Niech będzie instancją sumy podzbioru, gdzie jest listą (multiset) liczb, a jest sumą docelową. Niech . Niech jest lista utworzona przez dodanie do . $(L,B)$ $L$ $B$ $S = \sum L$ $L'$ $S+B,2S-B$ $L$

(1) Jeżeli istnieje podlista sumująca się do , wówczas można podzielić na dwie równe części: i . Rzeczywiście, pierwsza część sumuje się do , a druga do $M \subseteq L$ $B$ $L'$ $M \cup \{ 2S-B \}$ $L\setminus M \cup \{ S+B \}$ $B+(2S-B) = 2S$ . $(S-B)+(S+B) = 2S$

(2) W przypadku mogą być podzielone na dwie równe części , to nie ma podmenu sumowania do . Rzeczywiście, ponieważ a każda część sumuje się do , dwa elementy należą do różnych części. Bez utraty ogólności, . Reszta elementów w należy do $L'$ $P_1,P_2$ $L$ $B$ $(S+B)+(2S-B) = 3S$ $2S$ $2S-B \in P_1$ $P_1$ i suma . $L$ $B$

— Yuval Filmus
źródło

2

Ale średnia problemem podzbiorem sumy wykorzystuje wszystkie liczby całkowite i rozdzielono problemowe zastosowanie tylko nieujemne liczby całkowite ...

— gukoff

SUBSET-SUM jest NP-zupełny nawet z liczbami całkowitymi nieujemnymi, na przykład redukcja z 3SAT kończy się liczbami całkowitymi nieujemnymi. Prawdopodobnie istnieje również bezpośrednie zmniejszenie liczby całkowitej SUBSET-SUM do nieujemnej liczby całkowitej SUBSET-SUM.

— Yuval Filmus,

1

Tak, wiem i ta redukcja jest bardzo łatwa. Wystarczy zauważyć, że nie jest to suma podzbioru w jego „domyślnej” formie. :)

— gukoff,

Czy to też zadziałałoby, gdyby

To

? jako

, jak

L^{^{'}}

$L^{'}$

L ⋃ {B, S - B}

$L \bigcup \{B, S-B\}$

| {B, S - B} | = B

$|\{B, S-B\}| = B$

| L | = B

$|L| = B$

— Ciekawy

1

@ Issam Nie byłoby, to instancja PARTITION zawsze miałaby rozwiązanie

.

L, {B, S - B}

$L,\{B,S-B\}$

— Yuval Filmus

1

Odpowiedź wymieniona przez @Yuval Filmus jest niepoprawna (jest poprawna TYLKO, jeśli nie ma ujemnych liczb całkowitych). Rozważ następujący multiset:

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

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

a docelowa suma to . Wiemy, że nie ma podzbioru. Teraz tworzymy instancję dla problemu z partycją. Dwa nowe dodane elementy to i . Multiset ma teraz: a całkowita suma wynosi . $-2$ $2\sigma-t = 12$ $\sigma+t = 3$

{- 5, 2, 2, 2, 2, 2, 3, 12}

$\{-5, 2, 2, 2, 2, 2, 3, 12\}$

20

$20$

Problem partycji rozwiązuje odpowiedź, podając podzbiór Tutaj 2 nowe elementy znajdują się w tym samym podzbiorze (nie ma innego sposobu podziału na połowę sumy). Jest to zatem przykład przeciwny. Prawidłowa odpowiedź jest następująca:

{2, 2, 2, 2, 2}

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

Dodaj element, którego wartość wynosi . Łączna suma multisetu wynosi teraz . Rozwiąż problem z partycją, który da 2 podzbiory sumy . Tylko jedna partycja będzie zawierać nowy element. Wybieramy drugą partycję, której suma wynosi i rozwiązaliśmy problem podzestawu, redukując go do problemu partycji. To wyjaśnia link . $2t-\sigma$ $2t$ $t$ $t$

— Rohit Kumar Jena
źródło

1

Ale, jak mówi Yuval w komentarzu do swojej odpowiedzi, suma podzbiorów jest NP- zupełna, nawet jeśli ograniczymy się do dodatnich liczb całkowitych. Możemy więc założyć, że nie ma liczb ujemnych.

— David Richerby

1

Tak, zgadzam się, suma podzbiorów jest NP-zupełna nawet w przypadku dodatnich liczb całkowitych. Właśnie przedstawiłem pełniejszy dowód na liczbę całkowitą.

— Rohit Kumar Jena

1

„Po prostu dostarczenie pełniejszego dowodu”, a także błędne twierdzenie, że istniejąca odpowiedź jest nieprawidłowa.

— David Richerby,

1

Jest niepoprawny w tym sensie, że nie działa dla ujemnych liczb całkowitych. :) Pokój :)

— Rohit Kumar Jena

1

Oto prosty dowód:

$P_1,P_2$ $|X|$

$X$ $t$ $X'=X \cup \{s-2t\}$ $s=\sum_{x \in X}x$

( $\implies$ $S \subset X$ $t=\sum_{x \in S}x$
$s - t = \sum_{x \in S \cup {s - 2 t}} x,$ $\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$ $s - t = \sum_{x \in X^{'} ∖ (S \cup {s - 2 t})} x$ $\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$ $S\cup \{ s-2t \}$ $X' \setminus( S\cup \{s-2t\})$ $X'$
( $\impliedby$ $P_1',P_2'$ $X'$ $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$ $P_1$ $P_2$ $X$
$s - 2 t + \sum_{x \in P_{1}} x = \sum_{x \in P_{2}} x$ $\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$ $⟹ s - 2 t + \sum_{x \in P_{1}} x + \sum_{x \in P_{1}} x = \sum_{x \in P_{2}} x + \sum_{x \in P_{1}} x = s$ $\begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*}$ $⟹ s - 2 t + 2 \sum_{x \in P_{1}} x = s$ $\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$ $⟹ \sum_{x \in P_{1}} x = t$ $\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$

$t=\sum_{x \in S}x$ $P_1 =S\cup \{ s-2t \}$ $P_2=X' \setminus( S\cup \{s-2t\})$ $P_1',P_2'$ $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$ $f:(X,t)\rightarrow X'$ $(X,t)$ $\Leftrightarrow X'=f(X,t)$

— Pedrpan
źródło

0

Podzbiór Suma:

Dane wejściowe: {a1, a2, ..., am} st M = {1..m} i ai są nieujemnymi liczbami całkowitymi, a S⊆ {1..k} i Σai (i∈S) = t

Przegroda:

Dane wejściowe: {a1, a2, ..., am} i S⊆ {1, · · ·, m} st Σai (i∈S) = Σaj (j∉S)

Partycja N Dowód: jeśli prover zapewnia partycje (P1, P2) dla weryfikatora, weryfikator może łatwo obliczyć sumę P1 i P2 i sprawdzić, czy wynik wynosi 0 w czasie liniowym.

NP_Hard: SubsetSum ≤p PARTITION

Niech x będzie wejściem SubsetSum i x = 〈a1, a2, ..., am, t〉 i Σai (i od 1 do m) = a

Przypadek 1: 2t> = a:

Niech f (x) = 〈a1, a2, ..., am, am + 1〉 gdzie am + 1 = 2t − a

Chcemy pokazać, że x∈SubsetSum ⇔ f (x) ARTPARTITION

więc istnieją S⊆ {1, ..., m} st T = {1..m} - S i Σai (i∈T) = at

i Niech T '= {1 ... m, m + 1} - S więc Σaj (j∈T') = a-t + 2t-a = t

czyli dokładnie Σai (i∈S) = t i pokazuje f (x) ARTPARTITION

teraz Pokażemy również, że f (x) ARTPARTITION ⇔ x∈SubsetSum

więc istnieją S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S i Σai (i∈T) = [a + (2t-a ) -t] = t

i pokazuje Σai (i∈T) = Σaj (j∈S), więc m + 1∈T i S⊆ {1, · · ·, m} i Σai (i∈S) = t

więc x∈SubsetSum

Przypadek 2: 2t = <a :

możemy to sprawdzić, ale tym razem am + 1 to − 2t

— Behrooz Tabesh
źródło

-3

ten link ma dobry opis zarówno redukcji, podziału na sumę częściową, jak i sumy częściowej na partycję. Myślę, że jest to bardziej oczywiste niż odpowiedź YUVAL . przydatny link

— użytkownik44970
źródło

4

Nie publikuj odpowiedzi zawierających tylko linki. Jeśli treść linku zmieni się lub stanie się niedostępna, Twoja odpowiedź stanie się bezużyteczna. Zmień swoją odpowiedź tak, aby była użyteczna, nawet jeśli link jest niedostępny (na przykład przekształcenie treści własnymi słowami i podanie linku jako źródła i źródła).

— Tom van der Zanden