将混合子集合问题转换为全面情况

Question

假设我们有一个包含列表的子集 - 和问题{ $ x_1，x_2，x_3，... x_n $ }和权重 $ W $ ，其中一些 $ x_i <0 $ 。是否有一种已知的方法，在多项式时间中，将此问题转换为等效的问题，但是使用所有 $ x_i \ geq 0 $ ？如果没有任何，则可以存在这样的算法？

Answer 1

两个变体都是np-cleante，所以这样的减少肯定存在：np-confereness 保证它。

如果您想要显式减少，您可以将一个缩小到另一个（使用Cook的定理减少到3SAT，然后使用其NP完整性将3SAT减少到另一个）。然而，由此产生的减少将是丑陋的，所以我怀疑这可能不是您要找的。

如果您想要简单而自然，我不确定如何实现它。