Supercroissante (suite)

Imaginez des poids de 2, 3, 7, 20 et 45 unités. Chaque nouveau poids est plus lourd que tous ceux qui le précèdent réunis : 3 dépasse 2, 7 dépasse 2 + 3, et 20 dépasse 2 + 3 + 7.

Cette croissance laisse une trace très utile. Pour retrouver une somme, on regarde les poids du plus grand au plus petit et l'on garde un poids seulement s'il ne dépasse pas la somme restante. Ce choix glouton fonctionne parce qu'un terme est toujours trop grand pour être remplacé par tous les précédents.

Une suite supercroissante est une suite d'entiers positifs dans laquelle chaque terme dépasse strictement la somme de tous les termes qui le précèdent. Si aₙ désigne le terme de rang n, la condition s'écrit :

Les termes sont positifs et la comparaison porte sur tous les termes précédents, pas seulement sur le dernier. Cette condition rend chaque terme plus grand que toute somme formée avec les termes antérieurs. Elle s'applique directement au problème du sac à dos : étant donnée une suite de poids, il faut retrouver une somme en choisissant certains poids au plus une fois. Pour une suite supercroissante, une procédure gloutonne suffit et s'exécute en temps polynomial. La cryptographie a utilisé cette propriété, notamment dans le cryptosystème de Merkle-Hellman, mais les systèmes fondés sur cette idée ont été cassés.

Une suite supercroissante se décrit avec quatre éléments liés. Le premier terme fournit le point de départ. Chaque terme suivant est un entier positif. La somme cumulée rassemble tous les termes déjà rencontrés. Enfin, l'inégalité stricte compare le nouveau terme à cette somme cumulée.

Dans la suite 2, 3, 7, 20, 45, la somme cumulée vaut successivement 2, 5, 12 et 32 avant l'arrivée du terme suivant. Les dépendances sont essentielles : 7 est jugé par rapport à 2 + 3, puis 20 par rapport à 2 + 3 + 7. Les nombres et leur ordre définissent la structure ; une couleur ou une disposition sur une page ne la modifie pas. Ces données suffisent à vérifier la propriété et à construire l'ensemble ordonné des poids ; une cible doit encore être fournie pour définir l'instance de sac à dos associée.

Considérons la suite de poids 2, 3, 7, 20 et 45. On cherche les poids dont la somme vaut 32. Les données sont donc les cinq poids et la cible 32.

1. Le plus grand poids, 45, dépasse 32 ; il est écarté.
2. Le poids 20 ne dépasse pas la cible restante 32 ; il est retenu, et la cible restante devient 32 − 20 = 12.
3. Le poids 7 est retenu, car 7 ≤ 12 ; la cible restante devient 12 − 7 = 5.
4. Le poids 3 est retenu, car 3 ≤ 5 ; la cible restante devient 5 − 3 = 2.
5. Le poids 2 est retenu, car 2 ≤ 2 ; la cible restante devient 0.

La somme retrouvée est 20 + 7 + 3 + 2 = 32. Le contrôle consiste à refaire cette addition ; la cible est atteinte exactement, avec chaque poids choisi au plus une fois.

Dans une instance de sac à dos bâtie sur une suite supercroissante, on trie les poids par ordre décroissant, puis on compare chacun à la somme restante. Le poids est choisi s'il ne la dépasse pas. La somme restante n'est jamais négative et doit finir à zéro lorsque la cible est représentable.

Pour vérifier rapidement une suite, on conserve une somme cumulée. Dans 2, 3, 7, 20, 45, les tests sont 3 > 2, 7 > 5, 20 > 12 et 45 > 32. Un seul échec suffit à conclure que la suite donnée n'est pas supercroissante.

Lorsque la condition n'est pas satisfaite, la procédure gloutonne ne bénéficie plus de cette garantie. Il faut alors employer une méthode adaptée au problème de sac à dos considéré, au lieu de présenter le choix glouton comme universel.

Suite strictement croissante et suite supercroissante. Une suite strictement croissante exige seulement que chaque terme dépasse le précédent. Dans 2, 3, 4, les termes augmentent, mais 4 n'est pas supérieur à 2 + 3 = 5 : ce cas tranche entre les deux propriétés.

Somme de termes et dernier terme. La condition ne compare pas le terme suivant au seul dernier terme. Dans 2, 3, 7, le test correct est 7 > 2 + 3, et non simplement 7 > 3.

Un terme égal à la somme précédente. Dans 2, 3, 5, le dernier test donne 5 > 2 + 3, ce qui est faux car l'égalité est atteinte. Le mot « strictement » impose donc de rejeter cette suite.

Un terme plus petit que la somme précédente. Dans 2, 3, 4, le terme 4 est positif et supérieur à 3, mais 4 ≤ 2 + 3. La croissance ordinaire ne suffit pas ; il faut tester la somme complète des précédents.

Une cible non représentable. La procédure gloutonne garantit une résolution pour une instance associée à une suite supercroissante, mais une cible donnée peut ne pas être une somme des poids. Si la somme restante est strictement positive après le dernier poids, il faut constater l'absence de représentation au lieu d'inventer un choix.

La sécurité cryptographique ne découle pas de la propriété seule. Les suites supercroissantes ont servi dans des systèmes comme Merkle-Hellman, mais ces systèmes ont été cassés. La facilité du problème de sac à dos supercroissant ne suffit donc pas à garantir la sécurité d'un cryptosystème.

La fiche problème du sac à dos permet de replacer la suite supercroissante dans le problème de sélection de poids et de sommes.

La fiche cryptographie élargit la question de la protection des informations et aide à situer l'usage historique de Merkle-Hellman.