Problème de la somme de sous-ensembles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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é un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments 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 la partition d'un entier.

Exemple[modifier | modifier le code]

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

Généralisation[modifier | modifier le code]

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

Étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est s ?

Algorithmes de solution[modifier | modifier le code]

Algorithme exponentiel[modifier | modifier le code]

Algorithme pseudo-polynomial[modifier | modifier le code]

Algorithme d'approximation[modifier | modifier le code]

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.

Références[modifier | modifier le code]

  1. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill,‎ 2001, 2e éd. [détail de l’édition] (ISBN 0-262-03293-7, 978-0-262-03293-3 et 978-0-262-53196-2). Chapter 35.5, The subset-sum problem.
  2. Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, (ISBN 0-7167-1045-5).