混合サブセット和の問題を全否定的な場合に変換する

Question

リスト{span class="math-class"> $ x_1、x_2、x_3、... x_n $ }と重み $ w $ 、 $ x_i <0 $ のいくつかを使用します。この問題を同等の問題に変換するために、多項式の時点では既知の方法がありますが、すべての $ x_i \ geq 0 $ ？そしていずれかでなければ、そのようなアルゴリズムがあることが可能であるか？

Answer 1

両方の変形はNP完成であるので、このような減少は確かに存在します。NP完全さそれを保証します。

明示的な削減が必要な場合は、もう1つを減らすことができます（クックの定理を使用して3SATに縮小してから、そのNP完全性を使用して3SATをもう一方に減らす）。しかしながら、結果として生じる減少は醜いでしょう、それで私はこれがあなたが探しているものではないかもしれないと思うかもしれません。

あなたがシンプルで自然な削減を望むならば、私はそれをどのように達成するかはわからない。