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
modifierAvec une cible t
modifierLe 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
modifierLe 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
modifierLe 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é
modifierLe 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
modifierAlgorithme exponentiel
modifierAlgorithme pseudo-polynomial
modifierAlgorithme d'approximation
modifierUn 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
modifier- 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
modifier- (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).