Konvertieren eines gemischten Subset-Summenproblems in alle positiven Fall

Question

Nehmen wir an, wir haben ein Teilset-Sum-Problem mit der Liste { $ x_1, x_2, x_3, ... x_n $ } und Gewicht $ W $ , mit einigen von $ x_i <0 $ .Gibt es in der Polynomialzeit eine bekannte Weise, um dieses Problem in ein äquivalentes Problem umzuwandeln, jedoch mit allen $ x_i \ geq 0 $ ?Und wenn es nicht gibt, ist es möglich, dass es einen solchen Algorithmus gibt?

Answer 1

Beide Varianten sind NP-komplett, so dass eine solche Reduzierung sicherlich existiert: das Definition vonNP-Vollständigkeit garantiert es.

Wenn Sie eine explizite Reduktion wünschen, können Sie einen auf den anderen reduzieren (Reduzieren Sie den Satz auf 3sat mit Kochtheorem, und reduzieren Sie 3sat mit der NP-Vollständigkeit).Die resultierende Reduktion wird jedoch hässlich sein, also vermute ich, dass dies möglicherweise nicht das ist, wonach Sie suchen.

Wenn Sie eine einfache und natürliche Reduzierung wünschen, bin ich nicht sicher, wie ich es erreichen soll.