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 peut-être décrit de la manière suivante : étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est nulle ?

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.

Définition et exemple[modifier | modifier le code]

La définition formelle du problème est : étant donné un ensemble E de n entiers, existe-t-il un sous-ensemble de E dont la somme des éléments est nulle ?

Par exemple, pour l'ensemble {−7, −3, −2, 5, 8}, la réponse est oui car le sous-ensemble {–3, –2, 5} est de somme est nulle, par contre pour {-5,-1,2,3,7} la réponse est non.

Variantes et problèmes liés[modifier | modifier le code]

Avec une cible t[modifier | modifier le code]

Le problème de la somme de sous-ensembles peut être décrit avec une 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 ?

Cela revient au même car on peut enlever t à tous les éléments pour se ramener à 0.

Problème de la partition[modifier | modifier le code]

La problème de la partition (en) est un problème proche. Étant donné un ensemble E de n entiers, il faut décider si l'on peut partitionner E en deux ensembles de même somme.

3SUM[modifier | modifier le code]

Le problème 3SUM (en) est le suivant. Étant donné un ensemble E de n 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é[modifier | modifier le code]

Le problème est NP-complet[1]. On peut par exemple faire une réduction polynomiale au problème 3-SAT.

Algorithmes[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.

Notes et références[modifier | modifier le code]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ , 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9), «Problème de la somme de sous-ensemble» ,chap. 34.5.5, p. 979

Bibliographie[modifier | modifier le code]