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 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, [détail de l’édition], «Problème de la somme de sous-ensemble», chap. 35.5, p. 1007
- Sylvain Perifel, Complexité algorithmique, Ellipses, , 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, , 2e é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).