Aller au contenu

Autour de SubsetSum

Dans cette partie, tous les programmes sont à écrire en C.

On considère le problème \(\mathsf{SubsetSum}\) suivant :

Problème : SubsetSum

Entrées : un ensemble fini \(X \subset \N^*\) et \(T \in \N\).

Sortie : existe-t-il \(V \subset X\) tel que \(\sum_{x \in V} x = T\) ?

Les notions de problème de décision, de classe \(\mathbf{NP}\) et de réduction polynomiale sont celles du chapitre de calculabilité.

Vérification

Question 1. Écrire une fonction de prototype

bool subsetsum_solution(int *val, int nval, int tgt, bool *sol);

qui prend en entrée \(X\) donné sous la forme d'un tableau val de nval entiers et une solution donnée sous la forme d'un tableau sol de nval booléens où sol[i] vaut true si val[i] appartient à l'ensemble \(V\), et renvoie un booléen indiquant si la somme des éléments de \(V\) vaut tgt.

Corrigé 
bool subsetsum_solution(int *val, int nval, int tgt, bool *sol)
{
    int s = 0;

    for (int i = 0; i < nval; i++)
    {
        if(sol[i])
            s += val[i];
    }

    return s == tgt;
}

Question 2. Que peut-on en déduire pour le problème \(\mathsf{SubsetSum}\) ?

Corrigé

La solution donnée sous la forme d'un tableau de booléens est donc un certificat de taille polynomiale (ici linéaire : un bit par élément de \(X\)) en la taille de l'entrée, dont la vérification peut s'effectuer en temps polynomial : la fonction précédente fait \(n\) additions d'entiers dont la taille est majorée par celle de l'entrée.

On a donc \(\mathsf{SubsetSum} \in \mathbf{NP}\).

Recherche par force brute

Question 3. Écrire une fonction de prototype

void subsetsum_affiche(int *val, int nval, bool *sub);

qui prend en entrée \(X\) donné sous la forme d'un tableau val de nval entiers et un sous-ensemble \(V \subset X\) donné sous la forme d'un tableau sub de nval booléens où sub[i] vaut true si val[i] appartient à l'ensemble \(V\), et affiche \(V\) sur une ligne.

Exemple :

int val[] = { 1, 2, 4, 10 };
bool sub[] = { true, false, false, true };
subsetsum_affiche(val, 4, sub);

va afficher

1 10
Corrigé 
void subsetsum_affiche(int *val, int nval, bool *sub)
{
    for(int i = 0; i < nval; i++)
    {
        if(sub[i])
            printf("%d ", val[i]);
    }
    printf("\n");
}

Question 4. Écrire une fonction de prototype

void subsetsum_cherche_rec(int *val, int nval,
    int tgt, bool *sub, int i);

qui va considérer l'ensemble \(V\) décrit comme dans les questions précédentes mais avec

\[ V \subset \enscomp{ \text{val}[k]}{0 \le k < i} \]

et affiche récursivement \(V\cup V'\) pour toutes les solutions

\[ V' \subset \enscomp{ \text{val}[k]}{i \le k < \text{nval}} \]

à \(\mathsf{SubsetSum}\) pour la cible tgt.

Note : il s'agit donc de faire une simple recherche récursive par retour sur trace.

Corrigé 
void subsetsum_cherche_rec(int *val, int nval,
    int tgt, bool *sub, int i)
{
    if (i == nval) {
        if (subsetsum_solution(val, nval, tgt, sub))
            subsetsum_affiche(val, nval, sub);
    } else {
        sub[i] = true;
        subsetsum_cherche_rec(val, nval, tgt, sub, i+1);
        sub[i] = false;
        subsetsum_cherche_rec(val, nval, tgt, sub, i+1);
    }
}

Question 5. En déduire une fonction de prototype

void subsetsum_resout(int *val, int nval, int tgt);

qui affiche tous les sous-ensembles de val de somme tgt.

Corrigé

Il n'est pas nécessaire d'initialiser sub : chaque case sub[i] est affectée avant l'appel de rang i+1, donc avant toute lecture.

void subsetsum_resout(int *val, int nval, int tgt)
{
    bool *sub = malloc(sizeof(bool) * nval);
    subsetsum_cherche_rec(val,nval,tgt,sub,0);
    free(sub);
}

Par exemple, avec val contenant \(1, 2, \dots, 10\) et tgt valant \(12\), on obtient les \(13\) lignes 1 2 3 6, 1 2 4 5, 1 2 9, …, 5 7.

Question 6. Quelle est la complexité temporelle en pire cas de cette fonction ?

Corrigé

On suppose qu'on a \(n\) valeurs.

On énumère tous les sous-ensembles (\(2^n\) feuilles dans l'arbre des appels récursifs, et \(2^n - 1\) nœuds internes traités en temps constant) et chaque sous-ensemble est traité en \(O(n)\) pour vérifier qu'il convient (et éventuellement l'afficher). L'algorithme est donc en \(O(n 2^n)\).

NP-complétude

Dans cette partie, on note \(\mathcal{V}\) l'ensemble des variables propositionnelles et \(\mathbb{B} = \{ \top, \bot \}\) l'ensemble des valeurs de vérité.

On va montrer que \(\mathsf{SubsetSum}\) est NP-complet en réduisant polynomialement \(\mathsf{3SAT}\) à \(\mathsf{SubsetSum}\). On admet que \(\mathsf{3SAT}\) est NP-complet.

Problème : 3SAT

Entrées : une formule \(\varphi\) du calcul propositionnel donnée en forme normale conjonctive dont chaque clause comporte exactement trois littéraux.

Sortie : existe-t-il une valuation \(v : \mathcal{V} \rightarrow \mathbb{B}\) telle que \([\varphi]_v = \top\) ?

Question 7. Justifier qu'on peut supposer, sans perte de généralité, que la formule à résoudre par \(\mathsf{3SAT}\) est telle qu'aucune clause ne comporte à la fois un littéral et son littéral opposé.

Corrigé

Une telle clause est toujours satisfaite, quelle que soit la valuation (elle contient \(x \vee \neg x\)) : on peut donc l'omettre sans changer la satisfiabilité de la formule. Supprimer ces clauses se fait en temps linéaire et la formule obtenue est encore une entrée de \(\mathsf{3SAT}\).

On considère une formule \(\varphi = C_0 \wedge \dots \wedge C_{n-1}\) où \(\mathop{Var}(\varphi) = \{ x_0, \dots, x_{p-1} \}\) est l'ensemble des variables dont un littéral associé est présent dans au moins une clause. En vertu de la question précédente, on suppose également qu'aucune clause ne contient à la fois un littéral et son littéral opposé.

On associe :

  • à chaque variable \(x_i\), deux entiers \(a_i, a'_i\) définis par :

    \[ a_i = 10^{i} + \sum \enscomp{ 10^{p+j} }{ x_i \text{ littéral de } C_j, j \in \range{0}{n-1} } \]
    \[ a'_i = 10^{i} + \sum \enscomp{ 10^{p+j} }{ \neg x_i \text{ littéral de } C_j, j \in \range{0}{n-1} } \]

  • à chaque clause \(C_j\), deux entiers \(c_j = 10^{p+j}\) et \(c'_j = 2 \cdot 10^{p+j}\).

On pose alors \(X(\varphi) = \{ a_0, a'_0, \dots, a_{p-1}, a'_{p-1}, c_0, c'_0, \dots, c_{n-1}, c'_{n-1} \}\) et

\[ T(\varphi) = \sum_{i=0}^{p-1} 10^i + 4 \sum_{j=0}^{n-1} 10^{p+j} \]

Question 8. On considère la formule \(\varphi = C_0 \wedge C_1 \wedge C_2 \wedge C_3\) où \(C_0 = x_0 \vee \neg x_1 \vee \neg x_2\), \(C_1 = \neg x_0 \vee \neg x_1 \vee \neg x_2\), \(C_2 = \neg x_0 \vee \neg x_1 \vee x_2\) et \(C_3 = x_0 \vee x_1 \vee x_2\).

  1. Calculer \(X(\varphi)\) et \(T(\varphi)\).
  2. Résoudre \(\mathsf{SubsetSum}\) pour cette entrée.
  3. En déduire, si c'est possible, une valuation satisfaisant \(\varphi\).
Corrigé

  1. Ici \(p = 3\) et \(n = 4\). On a

    \[ a_0 = 1001001 \quad a'_0 = 110001 \]
    \[ a_1 = 1000010 \quad a'_1 = 111010 \]
    \[ a_2 = 1100100 \quad a'_2 = 11100 \]

    et \(c_0 = 1000, c'_0 = 2000, c_1 = 10000, c'_1 = 20000, c_2 = 100000, c'_2 = 200000, c_3 = 1000000, c'_3 = 2000000\).

    \(T(\varphi) = 4444111\).

  2. On trouve par exemple

    \[ \begin{array}{rcl} 4444111 &=& a_0 + a'_1 + a'_2 + c_3 + c'_3 + c_2 + c'_2 + c'_1 + c_0 \\ &=& 1001001 + 111010 + 11100 + 1000000 \\ && + 2000000 + 100000 + 200000 + 20000 + 1000 \end{array} \]

    L'instance est donc positive. Une recherche exhaustive (avec subsetsum_resout) donne en fait quatre solutions, qui correspondent aux quatre valuations satisfaisant \(\varphi\).

  3. On en déduit la valuation \(v(x_0) = \top\) et \(v(x_1) = v(x_2) = \bot\) (\(a_0\), \(a'_1\) et \(a'_2\) sont dans la somme). On vérifie rapidement qu'elle satisfait \(\varphi\) : \(x_0\) satisfait \(C_0\) et \(C_3\), \(\neg x_1\) satisfait \(C_1\) et \(C_2\).

Question 9. Justifier que cette réduction est polynomiale.

Corrigé

Chaque entier s'écrit avec au plus \(p+n\) chiffres et se calcule en temps linéaire en la taille de \(\varphi\) (un parcours des clauses), et il y en a \(2p + 2n\), nombre linéaire en la taille de \(\varphi\) (car \(p \le 3n\)), à calculer. De même pour \(T(\varphi)\). La réduction est donc calculable en temps quadratique.

Remarquons que ces \(2p+2n\) entiers sont deux à deux distincts : \(a_i\) et \(a'_i\) sont les seuls à avoir un chiffre non nul en position \(i < p\), et ils diffèrent car \(x_i\) apparaît dans au moins une clause et n'y apparaît pas avec son opposé ; \(c_j\) et \(c'_j\) n'ont qu'un chiffre non nul. L'ensemble \(X(\varphi)\) a donc bien \(2p + 2n\) éléments.

Question 10. Montrer que pour tout \(V \subset X(\varphi)\), il n'y a pas de retenue sur les chiffres de l'écriture décimale en calculant \(\sum_{v \in V} v\).

Corrigé

On remarque qu'il y a deux nombres ayant un \(1 \times 10^i\) dans leur écriture décimale pour \(i < p\) : \(a_i\) et \(a'_i\). Donc ce chiffre vaut 0, 1 ou 2 dans toute somme.

Le chiffre en position \(p+j\) vaut :

  • \(1\) dans au plus trois \(a_i\) ou \(a'_i\) (un par littéral de \(C_j\)) ;
  • \(1\) dans \(c_j\) ;
  • \(2\) dans \(c'_j\) ;
  • \(0\) dans tous les autres nombres.

On a donc au plus \(3 + 1 + 2 = 6\) pour ce chiffre dans toute somme. Comme chaque colonne a une somme inférieure ou égale à \(6 < 10\), il n'y a aucune retenue.

Ainsi, on pourra identifier le codage à des \((p+n)\)-uplets, si on le souhaite pour simplifier les preuves.

Question 11. Montrer que \(\varphi\) est satisfiable si et seulement s'il existe \(V \subset X(\varphi)\) tel que \(\sum_{v \in V} v = T(\varphi)\).

Corrigé

  • \(\Rightarrow\)) Soit \(v\) une valuation satisfaisant \(\varphi\), on considère \(V\) tel que

    • \(\forall i \in \range{0}{p-1}, a_i \in V\iff v(x_i) = \top\) ;
    • \(\forall i \in \range{0}{p-1}, a'_i \in V\iff v(x_i) = \bot\) ;

    • pour chaque clause \(C_j\),

      \[ V \cap \{ c_j, c'_j \} = \begin{cases} \{ c_j \} & \text{si } C_j \text{ a trois littéraux satisfaits}\\ \{ c'_j \} & \text{si } C_j \text{ a deux littéraux satisfaits}\\ \{ c_j,c'_j \} & \text{sinon} \end{cases} \]

      Comme la clause est satisfaite, ce « sinon » couvre uniquement le cas d'un seul littéral satisfait.

    Par construction, le \(i\)-ème chiffre de \(\sum V\) pour \(i < p\) est exactement \(1\) car chaque variable a une unique valeur de vérité. Pour les clauses, comme il y a un \(1\) par littéral satisfait dans les \(a_i, a'_i\), on rajoute exactement ce qu'il faut pour avoir 4 comme chiffre. Comme il n'y a pas de retenue, on a bien \(\sum V = T(\varphi)\).

  • \(\Leftarrow\)) S'il existe un tel ensemble \(V\), comme il n'y a pas de retenue, chaque chiffre de \(\sum V\) est la somme des chiffres correspondants des éléments de \(V\). Pour tout \(i \in \range{0}{p-1}\), on a forcément \(a_i \in V\) ou \(a'_i \in V\) mais pas les deux, car il y a un 1 au chiffre correspondant dans \(T(\varphi)\). On pose la valuation \(v(x_i) = \top\) si \(a_i \in V\), et \(\bot\) sinon. Ainsi, pour tout \(i\), \(a_i \in V\) si et seulement si \(x_i\) est satisfait par \(v\), et \(a'_i \in V\) si et seulement si \(\neg x_i\) est satisfait par \(v\).

    Soit \(C_j\) une clause : comme il y a le chiffre 4 en position \(p+j\) et que \(c_j + c'_j\) n'apporte que 3 à ce chiffre, c'est forcément qu'on a au moins un 1 provenant d'un des \(a_i\) ou \(a'_i\) présents dans \(V\), et donc \([C_j]_v = \top\) en considérant le littéral correspondant qui est nécessairement satisfait.

    Comme toutes les clauses sont satisfaites, \([\varphi]_v = \top\) et \(\varphi\) est satisfiable.

Question 12. En déduire que \(\mathsf{SubsetSum}\) est NP-complet.

Corrigé

On vient de montrer que \(\varphi \mapsto (X(\varphi), T(\varphi))\) (précédée de la suppression des clauses de la question 7) est une réduction polynomiale de \(\mathsf{3SAT}\) vers \(\mathsf{SubsetSum}\). Or \(\mathsf{3SAT}\) est NP-complet, donc pour tout \(p \in \mathbf{NP}\), \(p \le_P \mathsf{3SAT} \le_P \mathsf{SubsetSum}\) et, par transitivité, \(\mathsf{SubsetSum}\) est NP-difficile. Comme on a montré que \(\mathsf{SubsetSum}\) était dans \(\mathbf{NP}\), c'est un problème NP-complet.

Résolution par programmation dynamique

On considère ici un ensemble \(X = \{ x_0, \dots, x_{n-1} \} \subset \N^*\) et une valeur cible \(T \in \N\) et on cherche à calculer \(f(i,t)\) pour \(i \in \range{0}{n}\) et \(t \in \range{0}{T}\) tel que

\[ f(i,t) = \begin{cases} \top & \text{si } \exists I \subset \range{i}{n-1}, \sum_{k \in I} x_k = t \\ \bot & \text{sinon } \end{cases} \]

Question 13. Quelle valeur de \(f\) faut-il calculer pour résoudre cette instance de \(\mathsf{SubsetSum}\) ?

Corrigé

Il faut calculer \(f(0,T)\).

Question 14. Montrer qu'il y a des valeurs calculables directement pour \(f\) et d'autres valeurs qui satisfont une unique équation de récurrence, donc dans ce contexte une équation de Bellman.

Corrigé

On connaît les valeurs quand \(\range{i}{n-1} = \emptyset\), i.e. \(i = n\), car soit \(t = 0\) et la somme vide convient, soit c'est impossible.

\[ f(n, 0) = \top \quad \forall t \in \range{1}{T}, f(n, t) = \bot \]

On peut remarquer que la somme vide convient pour tout \(i\) donc

\[ \forall i \in \range{0}{n}, f(i, 0) = \top \]

Si \(i < n\) et \(t > 0\), on a deux possibilités pour réaliser \(t\) :

  • soit on prend \(x_i\) et on complète avec un sous-ensemble dont les indices sont dans \(\range{i+1}{n-1}\) et réalisant \(t - x_i\). Attention ce cas n'est valide que si \(t \ge x_i\).
  • soit on ignore \(x_i\) et on réalise \(t\) avec \(\range{i+1}{n-1}\).

Ainsi :

\[ f(i,t) = f(i+1,t) \vee \begin{cases} f(i+1,t-x_i) & \text{si } x_i \le t \\ \bot & \text{sinon} \end{cases} \]

Question 15. Écrire une fonction récursive qui calcule \(f\) de manière naïve.

Corrigé 
bool dyn_rec(int *val, int nval, int i, int t)
{
    if (t == 0)
        return true;
    if (i == nval)
        return false;
    bool b = dyn_rec(val, nval, i+1, t);
    if (val[i] <= t)
        b = b || dyn_rec(val, nval, i+1, t-val[i]);
    return b;
}

bool resout_dynrec(int *val, int nval, int tgt)
{
    return dyn_rec(val, nval, 0, tgt);
}

Chaque appel en fait au plus deux, donc cette fonction est en \(O(2^n)\). Cette borne est atteinte, par exemple pour \(x_k = 2(k+1)\) et \(T = n(n+1)+1\) : la cible restante est toujours impaire, donc jamais nulle, et strictement plus grande que la somme des valeurs restantes, donc l'arbre des appels est complet.

Question 16. On suppose donnés un type table et des fonctions :

table *create_table(); // crée une table vide
// teste si (i,t) est dans la table
bool has_couple(table *d, int i, int t);
// renvoie la valeur associée à (i,t) dans la table d
bool table_value(table *d, int i, int t);
// ajoute une correspondance (i, t) -> b
void table_add(table *d, int i, int t, bool b);
// libère la table
void free_table(table *d);

En déduire une version récursive efficace de \(f\).

Corrigé 
bool dyn_memo(int *val, int nval, table *d, int i, int t)
{
    if (has_couple(d, i, t))
        return table_value(d, i, t);

    bool b;
    if (t == 0)
        b = true;
    else if (i == nval)
        b = false;
    else {
        b = dyn_memo(val, nval, d, i+1, t);
        if (val[i] <= t)
            b = b || dyn_memo(val, nval, d, i+1, t-val[i]);
    }

    table_add(d, i, t, b);
    return b;
}

bool resout_dynmemo(int *val, int nval, int tgt)
{
    table *d = create_table();
    bool b = dyn_memo(val, nval, d, 0, tgt);
    free_table(d);
    return b;
}

Chaque couple \((i, t) \in \range{0}{n} \times \range{0}{T}\) n'est calculé qu'une fois : si les opérations sur la table sont en temps constant, on obtient une complexité en \(O(nT)\).

Question 17. Écrire une version tabulée de \(f\).

Corrigé

On range \(f(i,t)\) dans la case tab[i*(tgt+1)+t] d'un tableau de \((n+1)(T+1)\) booléens, rempli par \(i\) décroissant.

bool resout_dyntab(int *val, int nval, int tgt)
{
    bool *tab = malloc(sizeof(bool) * (nval+1) * (tgt+1));

    for(int t = 0; t <= tgt; t++)
    {
        tab[nval * (tgt+1) + t] = t == 0;
    }

    for(int i = nval-1; i >= 0; i--)
    {
        tab[i * (tgt+1)] = true;
        for(int t = 1; t <= tgt; t++)
        {
            bool b = tab[(i+1)*(tgt+1)+t];
            if(t >= val[i]) {
                b = b || tab[(i+1)*(tgt+1)+t-val[i]];
            }
            tab[i*(tgt+1)+t] = b;
        }
    }

    bool b = tab[tgt];
    free(tab);
    return b;
}

Question 18. On a ainsi calculé \(f\) avec une complexité en \(O(nT)\). A-t-on montré que P = NP ?

Corrigé

Non : \(O(nT)\) est polynomial en la valeur de \(T\), mais pas en la taille de l'entrée. Dans une représentation des entiers autre qu'en unaire (binaire, décimale…), \(T\) n'occupe que \(O(\log T)\) symboles : \(T\) est donc exponentiel en la taille de son écriture. On dit que cet algorithme est pseudo-polynomial. C'est précisément ce qui se passe pour la réduction précédente, où \(T(\varphi)\) vaut environ \(4 \cdot 10^{p+n-1}\).