Convertir un problema mixto de suma de subsetección a un caso todo positivo

Question

Digamos que tenemos un problema de suma de subsecreidad con la lista { $ x_1, x_2, x_3, ... x_n $ } y peso $ W $ , con algunos de $ x_i <0 $ .¿Hay alguna forma conocida, en el tiempo polinomial, para convertir este problema en un problema equivalente, pero con todos los $ x_i \ geq 0 $ ?Y si no hay ninguno, ¿es posible que haya un algoritmo?

Answer 1

Ambas variantes son NP-completadas, por lo que vale una reducción seguramente: la de definición deNP-integridad lo garantiza.

Si desea una reducción explícita, puede reducir una a la otra (reducir a 3SAT utilizando el teorema de COCK, luego reduzca 3SAT a la otra usando su integridad NP).Sin embargo, la reducción resultante será fea, por lo que sospecho que esto podría no ser lo que está buscando.

Si desea una reducción simple y natural, no estoy seguro de cómo lograrlo.