Problème de la somme d'un sous-ensemble

Problème de la somme de sous-ensembles

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.

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

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 ?

Algorithmes de solution

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 de N nombres x₁, x₂, ..., x_N et un nombre s, retourner

• oui, s'il y a un sous-ensemble dont la somme est s ;
• non, s'il n'y a pas de sous-ensemble dont la somme est entre (1-c)s et s pour un petit c>0 ;
• n'importe quoi, s'il y a un sous-ensemble dont la somme est entre (1-c)s et s, mais aucun dont la somme est s.

Si tous les nombres sont non négatifs, 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

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

Ce document provient de « Probl%C3%A8me de la somme de sous-ensembles ».