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

20

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!

dbonadiman
fonte

Respostas:

19

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 .(eu,B)euBS=eueuS+B,2S-Beu

(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 SMeuBeuM{2S-B}euM{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 BeuP1,P2euB(S+B)+(2S-B)=3S2S2S-BP1P1euB

Yuval Filmus
fonte
2
Mas o problema de soma subconjunto padrão usa todos os números inteiros, e usos problema de partição apenas inteiros não negativos ...
gukoff
SUBSET-SUM é NP-completo mesmo com números inteiros não negativos, por exemplo, a redução de 3SAT termina com números inteiros não negativos. Além disso, provavelmente há uma redução direta do número inteiro SUBSET-SUM para o número inteiro não negativo SUBSET-SUM.
Yuval Filmus
1
Sim, eu sei, e essa redução é muito fácil. Apenas observando que não é a soma do subconjunto no formulário "padrão". :)
gukoff
Também funcionaria se for ? como , como L{B,S-B}| {B,S-B}| =B| L| =Beueu{B,S-B}|{B,S-B}|=B|eu|=B
Curioso
1
@Issam Não, essa instância da PARTITION sempre teria a solução . eu,{B,S-B}
Yuval Filmus
1

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

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

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 } 2022σt=12σ+t=3

{5,2,2,2,2,2,3,12}
20

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:

{2,2,2,2,2}

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σ2ttt

Rohit Kumar Jena
fonte
1
Mas, como Yuval diz em um comentário à sua resposta, a soma do subconjunto é NP - completa mesmo se restringirmos a números inteiros positivos. Portanto, podemos assumir que não há números negativos.
David Richerby
1
Sim, eu concordo, a soma do subconjunto é NP-completa, mesmo no caso de números inteiros positivos. Eu estava apenas fornecendo uma prova mais completa para qualquer número inteiro.
precisa
1
"Apenas fornecendo uma prova mais completa" e também alegando erroneamente que uma resposta existente está incorreta.
David Richerby
1
É incorreto no sentido de que não funciona para números inteiros negativos. :) Paz :)
Rohit Kumar Jena /
1

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).P1,P2|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{s2t} onde s=xXx . Para ver que isso é uma redução:

  • () suponha que exista algum SX tal que t=xSx então teríamos que

    st=xS{s2t}x,
    st=xX(S{s2t})x
    e teríamos esse S{s2t} eX(S{s2t}) formar uma partição deX

  • () Suponha que exista uma partição P1,P2 de X tal que xP1x=xP2x . Observe que isso induz uma partição natural P1 e P2 de X tal modo que WLOG temos

    s-2t+xP1x=xP2x
    s-2t+xP1x+xP1x=xP2x+xP1x=s
    s-2t+2xP1x=s
    xP1x=t

Por isso, a partir de uma solução de t=xSx que pode formar um parition P1=S{s-2t} , P2=X(S{s-2t}) e, inversamente, a partir de uma partição P1,P2 podemos formar uma solução t=xP1{s-2t}xe, portanto, o mapeamentof:(X,t)X é uma redução (porque(X,t)está no idioma / conjunto SUBSETSUMX=f(X,t)é no idioma / set PARTITION) e fica claro que a transformação foi feita em tempo polinomial.

Pedrpan
fonte
0

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

Behrooz Tabesh
fonte
-3

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

user44970
fonte
4
Por favor, não poste respostas somente para links. Se o conteúdo do link mudar ou ficar indisponível, sua resposta se tornará inútil. Altere sua resposta para que seja útil, mesmo que o link esteja indisponível (por exemplo, redefinindo o conteúdo com suas próprias palavras e fornecendo o link como referência e fonte).
Tom van der Zanden