problème de partition

En informatique théorique, le problème de partition est le problème de décision qui, étant donné un multiensemble S d'entiers naturels, détermine s'il existe une partition de S en deux sous-ensembles S1 and S2 tels que la somme des éléments de S1 soit égale à la somme des éléments de S2. On ne connait pas d'algorithme en temps polynomial permettant de trouver une solution exacte rapidement dans tous les cas, c'est un problème NP-complet.