riducendo sottoinsieme-somma da divisorio

Question

sottoinsieme-sum: Dato un elenco di numeri, trovare se un elenco secondario non vuota ha sum 0 (c'è una variante in cui vogliamo somma = k invece di 0, ma 0 è più facile per l'analisi )

Partizione: Dato un elenco, può essere suddivisa in due sottoliste non vuoti con uguale somma

I vogliono ridurre sottoinsieme somma di partizione. Le riduzioni che ho trovato finora sono uguale a questo ma ha i seguenti difetti:

1. Per $ B = 0 $, è sempre possibile partizionare $ L '$ in $ \ {2S-0 \} $, $ \ {S + 0 \} U L $.
2. Si suppone $ 2S-B $ e $ S + B $ devono andare a partizioni diverse! Si potrebbe avere entrambi nella stessa partizione con elementi che somma $ -S $, somma da cui totale $ = 2S $ a seconda delle necessità.

Answer 1

1. Hai assolutamente ragione che questa partizione si verifica sempre. Se si considera ciò che questo significa in termini di sottoinsieme corrispondente, troverete che questo indica che l'insieme vuoto (che è sempre un sottoinsieme) ha somma 0. In realtà, questo indica che il c'è sempre una soluzione a somma sottoinsieme quando il bersaglio è 0, che è esattamente come previsto. Si scopre che fissa la somma di destinazione a 0 non si limita a rendere il problema più facile da discutere, si rende più facile in un senso di complessità ($ O (1) $ tramite emissione subito di sì).

2. Hai ragione anche qui. V'è una formulazione di somma sottoinsieme dove l'input è una lista di numeri interi positivi, e credo che la riduzione che si sta leggendo è stato da quella lingua. L'obiettivo era quello di avere i nostri elementi aggiunti essere abbastanza grande che non possono sia andare nella stessa parte. Per patch, possiamo utilizzare la somma dei valori assoluti. Questo dimostra in realtà parte della struttura della prova migliore, perché $ 2S $ era in realtà $ S + $ some-grande-abbastanza-numero-per-cui- $ S $ -Will-bastano-ma-so-do-di più ampio numeri.

A questo punto io sono copia-incolla dal post linked e solo la modifica ai negativi maniglia:

Sia $ (L, B) $ sia un'istanza di somma sottoinsieme, dove $ L $ è una lista (multinsieme) dei numeri, e $ B $ è la somma di destinazione. Sia $ S = \ sum L $ e scegli $ S'> \ sum_ {l \ in L} | l | $. Sia $ L '$ essere la lista formata con l'aggiunta di $ S' + B, S '+ S-B $ a $ L $.

(1) Se v'è un elenco secondario $ M \ subseteq L $ sommando a $ B $, allora $ L '$ può essere partizionato in due parti uguali: $ M \ tazza \ {S' + SB \} $ e $ L \ setminus M \ tazza \ {S '+ B \} $. Infatti, le prime somme parte a $ B + (S '+ S-B) = S' + S $, e il secondo per $ (S-B) + (S '+ B) = S' + S $.

(2) Se $ L '$ può essere suddivisa in due parti uguali $ P_1, P_2 $, allora v'è una lista parziale di $ L $ sommando a $ B $. La somma dei due nuovi elementi è $ (S '+ B) + (S' + S-B) = 2S '+ S $. Tutti i sottoinsiemi $ A \ subset L $ sono $ \ left | \ somma A \ right |