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, «Problème de la somme de sous-ensemble», chap. 35.5, , 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 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 : on peut par exemple lui réduire polynomialement le problème 3-SAT pp. 83−85, preuve de la Proposition 3-AH.
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
Bibliographie . 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, .
Somme de sous-ensembles Catégorie:Algorithme de cryptographie