Problème du sac à dos - Définition

La preuve de NP-complétude se fait en utilisant le problème de sac à dos sous la forme d'un problème de décision. Elle se fait en deux étapes, premièrement vérifier que (KP) appartient à la classe NP et, deuxièmement, montrer que (KP) est NP-difficile.

Nous utiliserons, pour la preuve d'appartenance à NP-difficile, la version somme de sous-ensembles (voir les variantes, plus bas), notée (SSE), une version particulière du sac à dos dans laquelle le profit d'un objet est égal à son poids. Si cette version particulière est NP-difficile, alors (KP) dans toute sa généralité l'est aussi.

Le problème (SSE) peut-être obtenu à partir du problème de sac à dos ci-dessus en posant w_i = p_i. En posant W = k, on obtient :

Trouver X tel que

• 
• 

Appartenance à NP

Premièrement, nous devons prouver que (KP) appartient à la classe NP, c’est-à-dire qu'il existe un algorithme polynomial qui, étant donné une solution au problème, peut vérifier que cette solution soit bonne. Pour vérifier une solution, il suffit de calculer la somme des poids des objets choisis et de la comparer avec W, ainsi que la somme de leurs valeurs, à comparer avec k. Le tout est évidemment polynomial. (KP) appartient donc à la classe des problèmes NP.

Appartenance à NP-difficile

Nous allons maintenant montrer que (SSE) est un problème NP-difficile en transformant le problème de la couverture exacte (noté (EC), de l'anglais exact cover) en un problème (SSE). Le problème (EC) s'exprime ainsi :

Soit U un ensemble d'éléments et un ensemble de sous-ensembles de U. Existe-t-il un sous-ensemble S ^* de S tel que :

•  : tous les éléments de U y soient ;
•  : chaque élément de U n'est que dans un seul des sous-ensembles choisis.

Le problème (EC) est NP-complet. Si nous arrivons à montrer que toute instance de (EC) peut être transformée polynomialement en une instance de (SSE) alors nous aurons prouvé que (SSE) (et donc (KP)) appartient à la classe des problèmes NP-difficiles.

Soit I = (U,S) une instance quelconque de (EC). Sans perdre de généralité, nous considérerons que . Nous noterons :

• l'état de l'ensemble S_i (x_i = 1 si et seulement si ) ;
• l'appartenance de la valeur j à l'ensemble S_i (y_ij = 1 si et seulement si ).

Soit b = | U | + 1. Les variables du problème (SSE) sont les x_i du problème (EC). Nous définissons leur poids de la façon suivante :

• .

Nous définissons la capacité W par

• .

Le poids de l'objet i est une somme de puissances de b et b^{j − 1} apparaît dans w_i si et seulement si . Par conséquent, il y a une correspondance de un à un entre la solution du problème (SSE) construit et l'instance de (EC). Chaque valeur w_i se calcule en O( | U | ) et la valeur de W se calcule en O(1). La transformation a donc une complexité temporelle en O(n | U | ). Le problème (SSE) (et donc le problème (KP)) appartient donc à la classe des problèmes NP-difficiles.

Conclusion

Nous avons prouvé que (KP) est dans NP et est NP-difficile. Par conséquent, le problème (KP) appartient à la classe des problèmes NP-complets.