Problème de la somme de sous-ensembles

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

Le problème de la somme de sous-ensembles aussi noté SSP (de l'anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est nulle ?

C'est un problème NP-complet et l'un des plus simples à décrire. Le problème de la somme des sous-ensembles peut être vu comme un cas particulier du problème du sac à dos. Un cas particulier du problème de la somme des sous-ensembles est le problème de partition.

[modifier] Exemple

On considère l'ensemble suivant : { −7, −3, −2, 5, 8}. Le problème admet une solution avec le sous-ensemble {-3, -2, 5} dont la somme est nulle.

On considère maintenant un autre ensemble : { -1, -2, -3}. Il est clair que le problème n'admet pas de solution (la somme est obligatoirement négative). Plus généralement, si tous les nombres sont strictement positifs ou tous les nombres sont strictement négatifs, alors le problème n'admet pas de solution (pour autant que la somme visée doit être nulle).

[modifier] Généralisation

Le problème de la somme de sous-ensembles peut être généralisé pour toute somme cible s, avec s un entier :

Étant donnés n entiers numérotés de 1 à n, ayant chacun une valeur, existe-t-il un sous-ensemble de ces éléments dont la somme des valeurs est s ?

[modifier] Références

T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, ISBN 0716710455.