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 $E$ de $n$ entiers, existe-t-il un sous-ensemble de $E$ 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 $t$ :

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

Problème de partition

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

3SUM

Le problème 3SUM (en) est le suivant. Étant donné un ensemble $E$ de $n$ 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 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

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

Bibliographie

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition]. Chapter 35.5, « The subset-sum problem ».
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, (ISBN 0-7167-1045-5).

Portail de la cryptologie
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[:0-1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition], «Problème de la somme de sous-ensemble», chap. 35.5, p. 1007

[2] Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne) pp. 83−85, preuve de la Proposition 3-AH