Sous-somme

Problème de déterminer si un sous-ensemble d’entiers a une somme donnée.

Problème de décision

• Instance :
  • Séquence $S=⟨x_1,...,x_n⟩$ d’entiers
  • Entier cible $k$
• Question : Existe-t-il $S^{\prime }\subseteq Stelque$\sum_{x \in S’} x = k$ ?

Complexité

Sous-somme est NP-complet.

Certificat

• Certificat de verification : Sous-ensemble $S^{\prime }\subseteq S$
• Vérification : Calculer ${\sum }_{x\in S^{\prime }}x$ et comparer à $k$

Réductions

Partition ${\ll }_P$​ Sous-somme

$f:⟨S⟩\to ⟨S,k=\frac{1}{2}{\sum }_{x\in S}x⟩$

Idée : Une partition équilibrée équivaut à trouver un sous-ensemble de somme égale à la moitié du total.

Sous-somme ${\ll }_P$​ Partition

$f:⟨S,k⟩\to ⟨S^{\prime }⟩$

Construction :

• $\sigma ={\sum }_{x\in S}x$
• $S^{\prime }=S\cup \{x_{n+1},x_{n+2}\}$
• $x_{n+1}=\sigma +k$
• $x_{n+2}=2\sigma -k$

Idée : Les deux nouveaux éléments ne peuvent pas être dans la même partition. Pour équilibrer, on doit prendre $k$ de $S$ avec $x_{n+1}$ et le reste avec $x_{n+2}$.

Sous-somme ${\ll }_P$​ Sac à dos (Knapsack)

Par transitivité : Sous-somme ${\ll }_P$​ Partition ${\ll }_P$​ Sac à dos

Ou directement : $f:⟨S,k⟩\to ⟨O=S,w=u=S,B=k,k⟩$