Conversione di un problema-somma del sottoinsieme misto per caso tutto positivo

Question

Diciamo che abbiamo un problema sum-sommatore con elenco { $ x_1, x_2, x_3, ... x_n $ } e peso $ W $ , con parte di $ x_i <0 $ .C'è un modo noto, in tempo polinomiale, per convertire questo problema in un problema equivalente, ma con tutte le $ x_i \ geq 0 $ ?E se non ce ne sono, è possibile che ci sia un tale algoritmo?

Answer 1

Entrambe le varianti sono NP-complete, quindi una tale riduzione esiste sicuramente: il Definizione diNP-Completezza La garantisce.

Se si desidera una riduzione esplicita, è possibile ridurre l'una all'altra (ridurre a 3sat utilizzando il teorema del cuoco, quindi ridurre 3SAT all'altro utilizzando la sua completezza NP).La riduzione risultante sarà brutta, però, quindi sospetto che questo potrebbe non essere quello che stai cercando.

Se si desidera una riduzione semplice e naturale, non sono sicuro di come raggiungerlo.