Convertendo um problema de soma de subconjunto misto para o caso totalmente positivo

Question

digamos que temos um problema de sombra de subconjunção com a lista { $ x_1, x_2, x_3, ... x_n $ } e peso $ W $ , com alguns de $ x_i <0 $ .Existe uma maneira conhecida, no tempo polinomial, para converter este problema em um problema equivalente, mas com toda a classe $ x_i \ geq 0 $ ?E se não houver, é possível que haja tal algoritmo?

Answer 1

Ambas as variantes são np-completos, então essa redução existe certamente: o definição deNP-completude garante.

Se você quiser uma redução explícita, você pode reduzir um para o outro (reduzir para 3sat usando o teorema do Cook, depois reduzir a 3,00 para o outro usando sua perfeição NP).A redução resultante será feia, no entanto, então eu suspeito que isso pode não ser o que você está procurando.

Se você quiser uma redução simples e natural, não tenho certeza de como alcançá-lo.