Problème de la somme de sous-ensembles

Le problème de la somme de sous-ensembles (en anglais : subset sum problem) est un problème de décision important en complexité algorithmique et en cryptologie. Le problème peut être décrit de la manière suivante : étant donné un ensemble de entiers, existe-t-il un sous-ensemble de dont la somme des éléments est nulle ? Par exemple, pour l'ensemble {-8, -3, -2, 4, 5}, la réponse est oui car la somme des éléments du sous-ensemble {-3, -2, 5} est nulle, par contre pour {-6, -1, 2, 3, 8} la réponse est non.

Le problème de la somme des sous-ensembles est NP-complet[1], c'est-à-dire considéré comme difficile à résoudre efficacement par un algorithme. Il peut être vu comme un cas particulier du problème du sac à dos.

Variantes et problèmes liés

Avec une cible t

Le problème de la somme de sous-ensembles peut être décrit avec une cible entière  :

Étant donné un ensemble de entiers, existe-t-il un sous-ensemble de dont la somme des éléments est  ?

Problème de partition

Le problème de partition est un problème proche. Étant donné un ensemble de entiers, il faut décider si l'on peut partitionner en deux ensembles de même somme.

3SUM

Le problème 3SUM (en) est le suivant. Étant donné un ensemble de entiers, existe-t-il trois entiers dont la somme est nulle ?

Ce problème peut être résolu facilement par programmation dynamique en temps O(n²), mais il est conjecturé que cette complexité est optimale. De nombreux problèmes, notamment en géométrie algorithmique sont prouvés 3SUM-difficiles.

Complexité

Le problème de la somme de sous-ensembles est NP-complet[1] : on peut par exemple lui réduire polynomialement le problème 3-SAT[1],[2].

Algorithmes

Algorithme exponentiel

Algorithme pseudo-polynomial

Algorithme d'approximation

Un algorithme d'approximation peut résoudre la version suivante du problème. Étant donné un ensemble E de N entiers et un entier s, retourner

  • oui, s'il y a un sous-ensemble de E dont la somme des éléments est s ;
  • non, s'il n'y a pas de sous-ensemble de E dont la somme des éléments est entre (1-c)s et s pour un petit c>0 ;
  • n'importe quoi, s'il y a un sous-ensemble de E dont la somme des éléments est entre (1-c)s et s, mais aucun dont la somme est s.

Si tous les nombres sont positifs ou nuls, la version approximative du problème de la somme de sous-ensembles se résout en temps polynomial en fonction de N et 1/c.

Notes et références

  1. ↑ a b et c Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], «Problème de la somme de sous-ensemble», chap. 35.5, p. 1007
  2. ↑ Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne) pp. 83−85, preuve de la Proposition 3-AH

Bibliographie