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, 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.