Exercice 5 - 3-SAT/SUBSET SUM

Le problème SUBSET SUM, est défini comme suit :

• Données : un ensemble $A = \{p_i \vert i \in \{1, \ldots, n\}\}$ de $n$ valeurs, une constante $K$.
• Question : existe-t-il un sous-ensemble $I$ de $\{1, \ldots, n\}$ tel que
  
  $$\Sigma_{i \in I}p_i = K?$$
  
  

On peut montrer par une réduction de $3-SAT$ que $SUBSET SUM$ est NP-Complet. Effectuons la transformation suivante :

• A chaque variable $x_j$, on associe deux valeurs $v_j$ et $v_j^\prime$ dont la représentation décimale comporte $p + n$ chiffres.
  • Les $p$ premiers chiffres représentent les clauses. Le $i$-ème chiffre ( $\in \{1, \ldots, p\}$) de $v_j$ prend la valeur $1$ si $x_j$ apparaît dans $C_i$, $0$ sinon. Le $i$-ème chiffre ( $\in \{1, \ldots, p\}$) de $v_j^\prime$ prend la valeur $1$ si $\neg x$ apparaît dans $C_i$, $0$ sinon.
  • Les $n$ derniers chiffres représentent l'indice de la variable $x_i$, le $p + j$-ème chiffre de $v_j$ et de $v_j^\prime$ prend la valeur $1$, les $n-1$ autres chiffres prennent la valeur $0$.
• A chaque clause $C_i$, on associe $2$ valeurs $x_i$ et $x_i^\prime$ de $n+p$ chiffres dont le $i$-ème chiffre vaut $1$ et tous les autres $0$.
• On prend comme nombre $K$ la valeur dont les $p$ premiers chiffres valent $3$ et les $n$ derniers $1$.

Utilisez la réduction polynomiale ci-dessus pour montrer que SUBSET SUM est NP-Complet.