Conversion d'un problème mixte sous-ensemble à un cas tout positif

Question

Disons que nous avons un problème de somme sous-ensemble avec la liste { $ x_1, x_2, x_3, ... x_n $ } et poids $ w $ , avec une partie de $ x_i <0 $ .Y a-t-il un moyen connu, en temps polynôme, de convertir ce problème en un problème équivalent, mais avec tout $ x_i \ geq 0 $ ?Et s'il n'y en a pas, est-il possible que là-bas soit un tel algorithme?

Answer 1

Les deux variantes sont NP-complètes, une telle réduction existe sûrement: le Définition deNP-Complêtement garantit-le.

Si vous souhaitez une réduction explicite, vous pouvez réduire l'un à l'autre (réduire à 3SAT à l'aide du théorème de COOK, puis réduisez 3SAT à l'autre à l'aide de son exhaustivité NP).La réduction résultante sera laide, cependant, je suppose que cela pourrait ne pas être ce que vous recherchez.

Si vous voulez une réduction simple et naturelle, je ne sais pas comment y parvenir.