Como posso reduzir a soma de subconjuntos para partição?

Talvez isso seja bastante simples, mas tenho alguns problemas para obter essa redução. Eu quero reduzir a soma de subconjuntos à partição, mas neste momento não vejo a relação!

É possível reduzir esse problema usando uma redução de Levin?

Se você não entende, escreva para esclarecimentos!

Seja uma instância da soma do subconjunto, onde é uma lista (conjunto múltiplo) de números e é a soma alvo. Deixe . Deixe- ser a lista formada por adição de a .$(L,B)$$L$$B$$S = \sum L$$L'$$S+B,2S-B$$L$

(1) Se houver uma sub-lista somando , então pode ser particionado em duas partes iguais: e . De fato, a primeira parte é somada a , e a segunda a .B L ′ M ∪ { 2 S - B } L ∖ M ∪ { S + B } B + ( 2 S - B ) = 2 S ( S - B ) + ( S + B ) = 2 $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) Se pode ser dividido em duas partes iguais , então existe uma sub-lista de soma de . De fato, desde que e cada parte é igual a , os dois elementos pertencem a partes diferentes. Sem perda de generalidade, . O resto dos elementos em P_1 pertence a L e soma para B .P 1 , P 2 L B ( S + B ) + ( 2 S - B ) = 3 S 2 S 2 S - B ∈ P 1 P 1 L $L'$$P_1,P_2$$L$$B$$(S+B)+(2S-B) = 3S$$2S$$2S-B \in P_1$$P_1$$L$$B$

A resposta mencionada por @Yuval Filmus está incorreta (está correta APENAS se não houver números inteiros negativos). Considere o seguinte multiset:

e a soma alvo é . Sabemos que não há subconjunto. Agora, construímos a instância para o problema da partição. Os dois novos elementos adicionados são e . O multiset agora é: e a soma total é .2 σ - t = 12 σ + t = 3 { - 5 , 2 , 2 , 2 , 2 , 2 , 3 , 12 } $-2$$2\sigma-t = 12$$\sigma+t = 3$

O problema da partição resolve a resposta, fornecendo o subconjunto Aqui, os 2 novos elementos estão no mesmo subconjunto (não há outra maneira de particionar na metade da soma). Portanto, este é um exemplo contrário. A resposta correta é a seguinte:

Adicione um elemento cujo valor seja . A soma total do multiset agora é . Resolva o problema de partição que fornecerá 2 subconjuntos da soma . Apenas uma das partições conterá o novo elemento. Escolhemos a outra partição cuja soma é e resolvemos o problema do subconjunto, reduzindo-o a um problema de partição. Isto é o que o link explica.$2t-\sigma$$2t$$t$$t$

Aqui está uma prova direta:

É fácil ver que SET-PARTITION pode ser verificado em tempo polinomial; dada uma partição apenas soma os dois e verifica se suas somas são iguais, o que obviamente é uma verificação de tempo polinomial (porque o somatório é uma operação polinomial e estamos executando apenas no máximo muitos somatórios).$P_1,P_2$$|X|$

O núcleo da prova está na redução de SUBSETSUM a PARTITION; para esse fim, dado o conjunto $X$ e um valor $t$ (a consulta de soma do subconjunto), formamos um novo conjunto $X'=X \cup \{s-2t\}$ onde $s=\sum_{x \in X}x$ . Para ver que isso é uma redução:

• ($\implies$) suponha que exista algum $S \subset X$ tal que $t=\sum_{x \in S}x$ então teríamos que

  $$\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$$ $$\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$$ e teríamos esse $S\cup \{ s-2t \}$ e$X' \setminus( S\cup \{s-2t\})$ formar uma partição de$X'$

• ($\impliedby$) Suponha que exista uma partição $P_1',P_2'$ de $X'$ tal que $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$ . Observe que isso induz uma partição natural $P_1$ e $P_2$ de $X$ tal modo que WLOG temos

  $$\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$$ $$\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*}$$ $$\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$$

Por isso, a partir de uma solução de $t=\sum_{x \in S}x$ que pode formar um parition $P_1 =S\cup \{ s-2t \}$ , $P_2=X' \setminus( S\cup \{s-2t\})$ e, inversamente, a partir de uma partição $P_1',P_2'$ podemos formar uma solução $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$e, portanto, o mapeamento$f:(X,t)\rightarrow X'$ é uma redução (porque$(X,t)$está no idioma / conjunto SUBSETSUM$\Leftrightarrow X'=f(X,t)$é no idioma / set PARTITION) e fica claro que a transformação foi feita em tempo polinomial.

Soma do subconjunto:

Entrada: {a1, a2, ..., am} st M = {1..m} e ai são números inteiros não negativos e S⊆ {1..k} e Σai (i∈S) = t

Partição:

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

Prova de partição Np: se o prover fornecer partições (P1, P2) para o verificador, o verificador poderá calcular facilmente a soma de P1 e P2 e verificar se o resultado é 0 em tempo linear.

NP_Hard: SubsetSum ≤p PARTITION

Seja x entrada de SubsetSum e x = 〈a1, a2, ..., am, t〉 e Σai (i de 1 para m) = a

Caso1: 2t> = a:

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

Queremos mostrar que x∈SubsetSum ⇔ f (x) ∈PARTITION

então existe S⊆ {1, ..., m} st T = {1..m} - S e Σai (i∈T) = em

e Seja T '= {1 ... m, m + 1} - S so Σaj (j∈T') = a-t + 2t-a = t

que é exatamente Σai (i∈S) = te mostra f (x) ∈PARTIÇÃO

Agora também mostraremos que f (x) TIPARTIÇÃO ⇔ x∈SubsetSum

então existem S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S e Σai (i∈T) = [a + (2t-a ) -t] = t

e mostra Σai (i∈T) = Σaj (j∈S), então m + 1∈T e S⊆ {1, · ·, m} e Σai (i∈S) = t

então x∈SubsetSum

Caso 2: 2t = <a :

podemos verificar o mesmo, mas desta vez am + 1 é − 2t

esse link tem uma boa descrição de ambas as reduções, partição para soma do subconjunto e soma do subconjunto para partição. Eu acho que é mais óbvio do que a resposta de YUVAL . link útil