Problèmes NP

Les classes de problèmes et leurs significations donnent toujours des problèmes aux étudiants. Ils ne sont certes pas aidés par la terminologie qui, lorsqu'elle n'est pas cryptique, peut induire en erreur. Nous allons tenter d'être le plus clair possible en n'introduisant que ce qu'il est nécessaire de jargon pour comprendre l'enjeu de cette classification.

En algorithmie théorique on ne peux pas utiliser la thèse de Church-Turing puisqu'elle n'est pas démontrée, ici on considérera que les algorithmes sont écrit en pseudo-code.

Problèmes utilisables en pratique

Un problème algorithmique implique qu'il existe un algorithme pour le résoudre On appelle ces problèmes calculables ou décidable. Comme on sait qu'il existe des problèmes non solvable par un algorithme (on a vu la complexité de Kolmogorov par exemple), on peut commencer par se restreindre aux problèmes décidables :

Mais parmi ces derniers, pour être utile en pratique, encore faut-il que l'on puisse les traiter en temps raisonnable (la durée d'une vie humaine par exemple). On va donner deux définitions du terme traiter. Commençons par la plus évidente : la résolution.

Résolution efficace

On a vu un certains nombre de problèmes polynomiaux, on peut par exemple citer :

• Trouver le maximum d'un tableau d'entiers dont on a démontré que sa complexité était linéaire,
• Trier un tableau d'entiers dont on a démontré que sa complexité était $\mathcal{O}(n\ln(n))$ où $n$ est la taille du tableau,

Le cas du problème de l'exponentiation est intéressant car on a démontré qu'il était en $\mathcal{O}(\ln(n))$ où $n$ est la valeur de l'exposant. Il n'est donc pas évident au premier coup d'œil que cela est bien polynomial en la taille des entrées, c'est à dire 2 entiers.

En informatique théorique l'unité d'information est le bit, la taille de l'entrée d'un algorithme est toujours égale au nombre de bits nécessaires pour la stocker. Pour un entier il s'agit donc du logarithme en base 2 de sa valeur et donc le problème de l'exponentiation est bien polynomiale, il est même linéaire en la taille de l'entrée...

Vérification efficace

Il existe de nombreux problèmes dont on ne connaît pas d'algorithme polynomiaux pour les résoudre mais la complexité, ou dont on ne connaît pas d'algorithmes polynomiaux pour les résoudre, mais dont dont sait facilement, grace à un algorithme efficace de vérification nommé vérifieur, voir si proposition de solution en est une ou pas.

Cette notion de vérification est cruciale. Si on ne sait pas construire de solutions nous même mais que quelqu'un arrive avec une solution potentielle, il faut pouvoir vérifier qu'elle est correcte avant de l'utiliser. Sans cette condition le problème n'a pas de solution réaliste : toute valeur peut être solution puisqu'on ne peut pas savoir avant d'essayer.

On peut voir le vérifieur comme une preuve (il y a équivalence entre preuve mathématique et algorithme, rappelons-le) automatisée et efficace (polynomiale, donc pouvant être écrite puis lue par des humains) de l'exactitude d'une solution.

Formalisons cette notion de vérification efficace :

Remarquez que l'on ne demande pas que sa complexité soit polynomiale par rapport à la sortie ! Seule, l'entrée compte.

Cependant, comme la complexité doit être polynomiale dans la taille de l'entrée cela implique que la taille de la sortie est polynomiale par rapport à la taille de l'entrée : si l'algorithme est de complexité $\mathcal{O}(|e|^k)$ alors seule $\mathcal{O}(|e|^k)$ bits de $s$ peuvent être examinés, cela ne sert à rien d'avoir des sorties plus longues.

Enfin, cette définition est réaliste puisque si l'on possède une solution on veut pouvoir vérifier de façon réaliste (ie. polynomialement) que c'est une solution : si sa taille est exponentielle, on ne peut même pas la lire en temps raisonnable !

Tout algorithme de $P$ admet un vérifieur efficace puisqu'il suffit d'exécuter l'algorithme de résolution et de vérifier si sa solution est égale à l'entrée.

Ainsi, pour le problème MAX (trouver le maximum d'un tableau) :

algorithme vérification_max(T: [entier], sol: entier) → booléen:
  m ← max(T)  # algorithme linaire trouvant le maximum d'un tableau
  rendre m == sol

Dans le cas d'algorithme de résolution linéaire (comme pour le problème de la recherche du maximum), cette approche est optimale. Mais pour des problèmes dont l'algorithme de résolution est non linéaire on peut souvent trouver un algorithme de vérification de complexité plus faible.

algorithme vérification_3_SUM(T: [entier], sol: (entier, entier, entier)) → booléen:
  i, j, k ← sol
  si T[i] + T[j] + T[k] == 0:
      rendre Vrai
  rendre Faux

Vérifieur efficace et algorithme de résolution

Les problème admettant un vérifieur ne sont pas forcément décidables. Considérons par exemple le vérifieur stop(E: chaîne, n: entier) → booléen qui rend vrai si le programme décrit par la chaîne de caractères E s'arrête au bout de n itération. Ce vérifieur correspond au problème de l'arrêt qui est indécidable.

Le fait que le problème admette un vérifieur dont la complexité ne dépend que du premier paramètre est donc cruciale. Si de plus sa complexité est polynomiale on a de plus :

La classe de Problèmes NP

Les problèmes utiles qui s'appellent en algorithmie les problèmes NP :

Ce qui donne le schéma suivant :

La définition ci-dessus appelle deux remarques :

• premièrement le nom a été très mal choisi. Il signifie Non Déterministe Polynomial (et pas du tout non polynomial...) car cette classe de problème peut être résoluble de façon polynomiale par des algorithmes non déterministes (un test si peut avoir plusieurs alors choisi de façon non déterministe). Dans ce cadre la définition fait sens puisqu'elle est identique à $P$ pour un autre type d'algorithme. Nous verrons ces types d'algorithmes plus tard.
• deuxièmement l'inclusion est stricte. Il existe des problèmes décidables qui ne sont pas dans NP. Ça aussi on le démontrera plus tard lorsque l'on étudiera .

On pourrait penser qu'il faudrait aussi borner la complexité spatiale. Utiliser un nombre exponentiel de mémoire étant tout autant rédhibitoire que d'utiliser un temps exponentiel.

La seule façon d'obtenir une complexité spatiale supérieure à la complexité temporelle est d'allouer de la mémoire (en $\mathcal{O}(1)$) et de ne jamais allez y voir (puisque y aller va consommer une opération). Par exemple allouer un tableau de $2^n$ cases et n'en utiliser que les cases $2^i$ : complexité spatiale exponentielle et temporelle polynomial. On gaspille un nombre exponentiel de mémoire.

On peut cependant changer cde genre d'algorithme grâce àla proposition suivante :

Structure de NP

Regardons la structure de NP d'un peu plus prêt en utilisant notre comparateur de problèmes : la réduction polynomiale.

De façon extrêmement surprenante lorsqu'on y pense, il existe un problème de $NP$, SAT, qui majore tous les autres problèmes. Nous démontrerons ceci précisément plus tard, admettons donc (pour l'instant) le théorème suivant :

C'est en effet surprenant qu'il n'y ait pas plusieurs élément maximaux de l'ordre induit par la réduction polynomiale.

Le problème SAT

Le problème SAT cherche à vérifier si une formule logique peut-être satisfaite.

Définitions

Pour cela, commençons par définir un concept fondamental en logique la conjonction de clauses :

Le problème SAT cherche à savoir s'il existe des valeurs pour lesquelles $f$ est vraie. Si telle est le cas, la conjonction de clause est dite satisfiable :

Exemple

Par exemple considérons les 4 clauses suivantes, sur 5 variables booléennes :

Il y $2^5 = 32$ possibilités (O ou 1 ; Vrai ou Faux) pour chaque variable. Essayons en quelques une :

• $x_1 = x_2 = x_3 = x_4 = x_5 = 0$ ne permet pas de satisfaire la formule car $x_1 \lor {x_2} = 0$
• $x_1 = x_2 = x_3 =x_4 = x_5 = 1$ non plus ($\overline{x_1} \lor \overline{x_2} \lor \overline{x_3} = 0$)
• $x_1 = \overline{x_2} = x_3 = \overline{x_4} = x_5 = 1$ fonctionne

La formule précédente est satisfiable !

SAT est dans NP

Pour montrer que le problème SAT est dans NP, il faut exhiber un vérifieur polynomial c'est à dire un algorithme. Il faut donc pouvoir transformer une instance "papier" de SAT en une entrée d'un programme. Il y a plusieurs façon de faire, nous allons en montrer une simple à mettre en oeuvre.

Une instance de SAT est composée :

• $x_1, \dots, x_n$ : les $n$ variables booléennes
• $c_1 \land \dots \land c_m$ : les $m$ conjonctions de clauses
• $c_i = l^1_i \lor \dots \lor l^{k_i}_i$ : les littéraux formant les clauses.

La conversion vers une entrée d/un algorithme se fera ainsi :

• on associe l'entier $i$ à la variable $x_i$
• une clause $c_i$ sera un tableau $T_i$ de longueur égal $k_i$ à son nombre de littéraux
• $T_i[j] = k$ si $l_i^j = x_k$ et $T_i[j] = -k$ si $l_i^j = \overline{x_k}$
• la conjonction de clause sera un tableau de tableau d'entier de taille $m$ (le no,bre de clauses)

[[1, 2],
 [-1, -2, -3],
 [-1, 3, 4, -5],
 [1, -3, -4, 5]
]

Avec cet encodage, une solution de SAT sera un tableau de booléen $S$ de longueur $n$ tel que $x_i = S[i-1]$.

Par exemple pour la solution $x_1 = \overline{x_2} = x_3 = \overline{x_4} = x_5 = 1$ de l'exemple, on aura : S = [Vrai, Faux, Vrai, Faux, Vrai]

Avec un tel encodage, il est facile de créer un vérifieur linéaire à un problème SAT, faites le :

algorithme vérif_SAT(conj_clauses: [[entier]], # [c_1, ..., c_m]
                     solution: [booléen]) # [x_1, ..., x_n]
                     → booléen:
    pour chaque c de conj_clauses:
        sat ← Faux
        pour chaque l de c:
            si l > 0 ET solution[l-1]:
                sat ← Vrai
            si l < 0 et (solution[l-1] == Faux):
                sat ← Vrai
        si sat == Faux:
            rendre Faux
    rendre Vrai

Même s'il est facile de vérifier si une solution potentielle est une solution, on ne connaît pas d'algorithme polynomial pour résoudre SAT. L'algorithme naïf consistant à tester toutes les solutions possibles prendrait $\mathcal{O}(mn\cdot 2^n)$ opérations ($2^n$ possibilités pour les variables et la taille d'une conjonction de clause est $nm$). Aussi surprenant que cela paraisse, on ne connaît pas d'algorithme fondamentalement meilleur :

Réduction vers SAT

Le théorème de Cook et Leven stipule que tout problème de NP peut se réduire à un cas particulier du problème SAT. Pour démontrer cela ils montrent que tout problème algorithme de NP peut s'écrire polynomialement comme une formule SAT qui n'est satisfiable que pour des solutions du problème initial.

Nous ne démontrerons pas ici ce théorème mais allons montrer quelques exemples pour que vous puissiez appréhender ce résultat fondamental.

Nous allons aussi utiliser le fait que toute formule logique peut se mettre efficacement sous la forme d'une disjonction de clause grâce à la transformation de Tseitin que nous étudierons un peut plus tard. Ceci nous permet d'uniquement chercher une formule logique, pas forcément une disjonction de clauses.

MAX

Montrons que l'on peut le faire pour le problème MAX (trouver le maximum d'un tableau). Le but de cette réduction est de passer de la comparaison d'entiers à la comparaisons de variables booléennes. Nous allons faire ça en plusieurs étapes.

1. l'égalité $(x^i = y^i)$ pour deux variables booléennes s'écrit $(x^i = y^i) \coloneqq (x^i \land y^i) \lor (\overline{x^i} \land \overline{y^i})$. La formule logique est n'vrai que si les deux variables booléennes sont égales.
2. un entier $x$ peut s'écrire sous sa forme binaire $x^px^{p-1}\dots x^0$ où $x^i \in \{0, 1\}$ et $x = \sum_{0\leq i \leq p}x^i2^i$

Des deux remarques précédentes, on en déduit que le test $(x = y)$ pour deux entiers s'écrit par le fait que tous les bits sont égaux (on suppose que l'on écrit nos entiers avec le même nombre de bits $p$, quitte à mettre des 0 en fin de tableau pour le plus petit):

De là, l'inégalité $(x > y)$ pour deux entiers s'écrit par le fait qu'il existe $k$ tel que les k-1 derniers bits sont égaux et le $k$ème bit de x est plus grand que celui de x, c'est à dire que $x^k = 1$ et $y^k = 0$ :

Ce qui s'écrit aussi :

On en déduit la formule logique associé à l'inégalité :

Enfin, pour avoir $(x \geq y)$ on combine les deux formules :

Ceci nous permet d'écrire la formule logique permettant de décrire un problème MAX est :

Puisque l'équation logique ci-dessus vérifie si $T[i]$ est le plus grand des éléments du tableaux pour tout $i$.

A priori, ce n'est pas encore fini puisque la formule logique n'est pas sous la forme d'une conjonction de clause. Mais on sait que l'on peut utiliser la transformation de Tseitin pour transformer cette formule logique en une conjonction de clauses ce qui montre que le problème MAX peut se résoudre via le problème SAT.

Addition de 2 bits

L'exemple précédent était éclairant mais pas forcément bluffant : le problème MAX pouvant se représenter facilement comme une succession de tests logiques. Nous allons donc aller un peu plus loin et transformer un algorithme, la somme de deux nombres binaires en une conjonction de clause.

Commençons par quelque chose de simple, l'addition de 2 bits :

algorithme somme_binaire(x: bit,
                         y: bit)
                         → [bit]  # somme = T[0] + 2 * T[1]
    somme ← [0, 0]
    si (x == 1) et (y == 1):
        rendre [0, 1]             # le nombre 10
    si (x == 1) ou (y == 1):
        rendre [1, 0]             # le nombre 01
    rendre [0, 0]                 # le nombre 00

Le corps de l'algorithme peut s'écrire avec la formule logique suivante, en notant la sortie de l'algorithme $z = [z^0, z^1]$ :

Pour exécuter l'algorithme il faut donner des valeurs aux entrées $x$ et $y$. Par exemple si $x=1$ et $y=0$, la formule logique à satisfaire est :

Elle ne peut avoir comme solution que :

• $x=1$ et $y=0$ : c'est nos entrées que l'on a forcé
• $z^0 = 0$ et $z^1 = 1$ : la sortie est impliquée par la formule

À vous :

On y reviendra, mais remarquez que la formule associée à l'algorithme est symétrique. On peut très bien fixer la sortie pour trouver l'entrée. Par exemple si l'on cherche à trouver pour quelles valeurs de $x$ et $y$ on peut obtenir $z^0 = 1$ et $z^1 = 0$ il faut résoudre la formule :

Et on trouvera $x=1$ et $y=1$.

À vous :

Addition de 2 entiers

Tout comme pour le problème du max si on veut additionner deux entiers on les transforme en variables binaire en utilisant le fait qu'un entier $x$ peut s'écrire sous sa forme binaire $x^px^{p-1}\dots x^0$ où $x^i \in \{0, 1\}$ et $x = \sum_{0\leq i \leq p}x^i2^i$. On considère l'algorithme suivant qui généralise l'addition sur 1 bit :

algorithme somme_binaire(x: [bit],
                         y: [bit])  # on suppose x et y de même taille
                         → [bit]  # de la taille de x et y + 1

    somme ← un tableau de taille x.longueur + 1 bits
    retenues ← un tableau de taille x.longueur + 1 bits
    retenues[0]  ← 0

    pour chaque i de [0 .. x.longueur - 1[:
        si (x[i] == 1) et (y[i] == 1) et (retenues[i] == 1):
            somme[i]  ← 1
            retenues[i + 1]  ← 1
        sinon si ((x[i] == 1) et (retenues[i] == 1)) ou ((y[i] == 1) et (retenues[i] == 1)) ou ((x[i] == 1) et (y[i] == 1)):
            somme[i]  ← 0
            retenues[i + 1]  ← 1
        sinon si (x[i] == 1) ou (y[i] == 1) ou (retenues[i] == 1):
            somme[i]  ← 1
            retenues[i + 1]  ← 0
        sinon:
            somme[i]  ← 0
            retenues[i + 1]  ← 0
    somme[x.longueur] ← retenues[x.longueur]
    rendre somme

L'algorithme ci-dessus est une implémentation binaire de l'addition posée que l'on apprend au primaire. L'addition des nombres x = 1011 et y = 0111 donne somme = 10011 :

   1011  = 11     x
+  0111  =  7     y
  11110           retenue
------------
  10010  = 18     somme

Pour l'algorithme on a comme entrée x=[1,1,0,1] et y=[1,1,1,0] et on doit avoir [0,1,0,0,1] comme sortie.

On peut maintenant convertir cet algorithme en une formule logique. On va utiliser les variables binaires :

• $x^0, \dots, x^{p}$ pour représenter $x = \sum_{0\leq i \leq p}x^i2^i$,
• $y^0, \dots, y^{p}$ pour représenter $y = \sum_{0\leq i \leq p}y^i2^i$,
• $s^0, \dots, s^{p+1}$ pour représenter la somme $x+y = s = \sum_{0\leq i \leq p+1}s^i2^i$,
• $r^0, \dots, r^{p+1}$ pour représenter les retenues.

Commençons par représenter une itération de la boucle pour chaque sous la forme d'une formule :

Ce qui est remarquable dans cet algorithme c'est que chaque variable n'est affecté qu'une seule fois. On peut donc directement écrire l'algorithme en remarquant que chaque itération est un ET :

L'algorithme sous la forme d'une formule est maintenant capable d'additionner 1011 et 0111. Il suffit de les mettre "en entrée" de la formule :

Algorithme et SAT

Levin et cook que ce principe de transformation d'un algorithme en formule est applicable à tout pseudo-code en tenant en compte l'évolution des variables au cours des instructions, ce que nous n'avons pas eu besoin de faire dans nos deux exemples car chaque variable n'est assignée qu'une seule fois.

Problèmes NP-Complet

Le théorème de Levin et Cook stipule que tout problème de NP peut se réduire polynomialement à un cas particulier de SAT : le problème SAT est un élément maximal de l'ordre entre problèmes de NP induit par la réduction polynomiale. Ce théorème montre l'existence de problèmes universels, on les appelle NP-complet, dont tous les autres problèmes ne sont que des cas particuliers :

Cette définition est consistante car deux problèmes différents de NP peuvent êtres tels que $A \leq B$ et $B \leq A$ (on l'a vu pour 3-SUM' et 3-SUM par exemple). Rien n'empêche donc d'avoir plusieurs problèmes se comportant comme SAT, La structure de NP est donc maintenant la suivante :

Fixons nous les idées en démontrant que le problème suivant est NP-complet.

Couverture Exacte est NP-complet

Illustrons ce problème en reprenant un exemple tiré de Wikipédia :

• $U = \{1, 2, 3, 4, 5, 6, 7\}$
• $\mathcal{S} = \{ \{1, 4, 7\}, \{1, 4\}, \{4, 5, 7\},\{3, 5, 6\},\{2, 3, 6, 7\},\{2, 7\} \}$

Résoudre ce problème revient à faire plein de choix. Parfois ces choix sont simple : si on place $\{1, 4, 7\}$ on ne peut plus mettre que la classe $\{3, 5, 6\}$ qui ne forme pas une partition ; parfois les choix sont plus cornéliens : doit-on placer la classe $\{3, 5, 6\}$, ce qui empêche d'utiliser la classe $\{4, 5, 7\}$ (par exemple) ? Ou ne pas la mettre ? A priori on ne sais pas.

Prouver que le problème de Couverture Exact (CE) est NP-Complet va être plus facile que celle du théorème de Cook/Levin. En effet, maintenant que l'ensemble des problème NP-complet est non vide (il y a au moins SAT dedans), pour montrer qu'un problème $A$ est NP-complet il nous suffit maintenant de :

1. choisir un problème $B$ NP-complet
2. montrer qu'il existe une réduction polynomiale $B \leq A$

En effet, si $C$ est un problème quelconque de NP, on a $C\leq B$ (par définition de l'ensemble NP-complet) ce qui amène par transitivité de la réduction polynomiale à $C \leq A$.

Pour l'instant nous ne connaissons qu'un problème NP-Complet : SAT. Montrons donc que $SAT \leq CE$.

Les réductions pour montrer qu'un problème est NP-complet peuvent être étrange au premier regard. Elles nécessitent souvent des constructions baroques pour associer un problème à l'autre. On appelle ces constructions des gadget. Ceci est normal car on essaie de mettre en regard deux problèmes qui n'ont souvent rien à voir. On va le faire ici en mettant en parallèle un problème de logique SAT et un problème de recherche de sous-ensemble CE.

Gadget

On considère une instance de SAT que l'on va transformer polynomialement en une instance de CE. Posons ses paramètres :

• $x_1, \dots, x_n$ : les $n$ variables booléennes
• $c_1 \land \dots \land c_m$ : les $m$ conjonctions de clauses
• $c_i = l^1_i \lor \dots \lor l^{k_i}_i$ : les littéraux formant les clauses.

On suppose de plus sans perte de généralité que :

1. il n'existe pas de clause ayant à la fois $x_i$ et $\overline{x_i}$ comme littéral (sinon cette clause est trivialement toujours vérifiée)
2. pour toute variable booléenne $x_i$ il existe une clause ayant $x_i$ comme littéral et une autre clause ayant $\overline{x_i}$ (sinon il suffit de mettre la modalité de $x_i$ à celle apparaissant dans les clauses pour les rendre trivialement vraies)

Notez que l'on peut transformer toute instance de $SAT$ en une instance satisfaisant les deux conditions ci-dessus en supprimant les clauses satisfaisant la première condition et en supprimant la variable booléenne satisfaisant la seconde condition. Cette transformation se fait en temps polynomial par rapport à l'entrée de $SAT$.

On peut maintenant transformer cette instance de $SAT$ en une instance de $CE$ ayant comme entrée :

L'ensemble de $CE$ couvre tous les éléments de $SAT$ : les variables booléennes, les clauses et les littéraux. Les classes forment les liens entre les différents éléments : pour chaque $x_i$ les littéraux valant $x_i$, pour chaque $x_i$ les littéraux valant $\overline{x_i}$ et pour chaque clause l'ensemble de ses littéraux. Cette construction est bien polynomiale par rapport à la taille de l'entrée du problème $SAT$.

Notre gadget transforme L'instance exemple SAT en une instance de $CE$.

Formule SAT originelle :

Entrée de CE associée :

Nous allons montrer sur l'exemple que ce gadget fonctionne. Je cas général en découlera de lui-même.

de CE vers SAT

Pour comprendre comment une solution de CE permet de trouver une solution de SAT, reprenons notre exemple et cherchons une partition solution. Il en existe plusieurs, par exemple :

Pour repasser de cette solution de CE à une solution de SAT, regardons comment elle est construite :

• il faut que la partition contienne les $c_i$ : de part la construction de $\mathcal{S}$ ceci signifie que la classe contenant $c_i$ va également contenir 1 $l_i^j$.
• il faut que la partition contienne les $x_i$ : de part la construction de $\mathcal{S}$ ceci signifie que la classe contenant $x_i$ va également contenir des $l_j^k$. Attention ces $l_j^k$ ne doivent pas être celui choisi dans la classe contenant $c_j$
• tous les autres littéraux pouvant être attribués comme on le souhaite on peut les "oublier".

Pour notre exemple ceci donne :

Remarquez que le choix de la classe contenant la clause contraint la classe contenant la variable. En choisissant $\{c_1, l_1^1\}$ je force le choix de $\{x_1, l_2^1, l_3^1\}$ puisque $l_1^1 = x_1$. Vous venez de découvrir le gadget : la classe contenant $c_i$ force le choix pour $x_j$ en prenant le littéral opposé.

Comme une solution de SAT doit avoir au moins 1 littéral de vrai par clause, regardons ce qu'il se passe si on suppose que c'est celui choisi dans la clause est vrai. Dans l'exemple :

• $l_1^1$ est vrai donc $x_1$ est vrai
• $l_2^2$ est vrai donc $\overline{x_2}$ est vrai
• $l_3^2$ est vrai donc ${x_3}$ est vrai
• $l_4^1$ est vrai donc ${x_1}$ est vrai

On ne peut pas arriver àla conclusion qu'une variable booléenne est vrai et fausse, car sinon il est impossible de choisir une classe contenant cette variable : c'est le principe du gadget qui implique que ces choix sont cohérents avec les classes contenant les $x_i$ (qui correspondent aux littéraux faux).

On sait déjà que $x_1$, $\overline{x_2}$ et ${x_3}$ sont vrais. Pour connaître la valeur des autres variables, on regarde les classes choisies :

• ${x_1, l_2^1, l_3^1}$ donc $l_2^1 = \overline{x_1}$ et $l_3^1 = \overline{x_1}$ sont faux donc $x_1$ est vrai (ouf, c'est cohérent)
• ${x_2, l_1^2}$ donc $l_1^2 = {x_2}$ est faux (c'est cohérent)
• ${x_3, l_2^3, l_4^2}$ donc $l_2^3 = l_4^2 = \overline{x_3}$ est faux : $x_3$ est vrai (c'est cohérent)
• ${x_4, l_3^3}$ donc $l_3^3 = {x_4}$ est faux. On ne le savait pas encore
• ${x_5, l_3^4}$ donc $l_2^3 = l_3^4 = \overline{x_5}$ est faux : ${x_5}$ est vrai.

Au final, avoir une partition nous garantit que le problème SAT originel a une solution et la donne !

On reconstruit cette solution en temps (clairement) polynomial.

de SAT vers CE

Il faut maintenant montrer la réciproque : si notre instance de $SAT$ à une solution alors notre instance de $CE$ en a également une.

Il suffit de faire la même chose que pour l'analyse précédente. Si l'instance de SAT a une solution, chaque clause $c_i$ possède au moins un littéral $l_i^{v(i)}$ qui est vrai. On peut alors considérer l'ensemble des classes formé de l'union de :

• $\{c_i, l_i^{v(i)}\}$ pour tout $ 1\leq i \leq m$,
• Considérons ensuite chaque littéral $l_i^j$ avec $ j \neq v(i)$ pour la solution de SAT. On a deux cas :
  • soit $l_i^j$ est vrai et on ajoute $\{ l_i^j\}$ à la solution de $CE$
  • soit $l_i^j$ est faux et on ajoute l'unique classe de $\mathcal{F}$ contenant $\{x_i, l_i^j\}$ à la solution de $CE$

De part nos hypothèses sur l'entrée de $SAT$ il est clair que cet ensemble de classes forme une solution à notre problème de $CE$. De plus, la construction de cette solution est bien polynomiale.

Conclusion

On vient de prouver $SAT\leq CE$ car :

1. $CE$ est dans NP
2. il existe une réduction polynomiale de SAT vers CE

On a trouvé un deuxième élément à la classe des problèmes NP-complets !

Que signifie NP-complet

Il existe un grand nombre de problèmes NP-complet. Juste après la démonstration de Levin et Cook en 1971, Karp démontrait en 1972 qu'il y en avait au moins 21 de plus ! Et on ne cesse d'en découvrir d'autres.

Comme tout problème de NP est un cas particulier de tout problème de NP, ceci signifie ces problèmes sont universels. D'un point de vue algorithmique ceci signifie qu'il n'y a pas de lien polynomial entre les entrées et les solutions : ce sont des problèmes sans structure, il n'y a pas de balle en argent pour résoudre magiquement le problème. Il faut tout essayer.

P et NP

Si les problèmes de $P$ sont inclus dans $NP$, on ne sait pas si l'inclusion est stricte. On a implicitement supposé que les problèmes NP-complets ne sont pas dans P, mais en vrai on en sait rien : la question est ouverte ! Certains se demandent même si cette question est décidable (ie. démontrable).

Ce qui est en revanche sur c'est que tout le monde espère que c'est vrai car sinon tout code informatique devient facilement déchiffrable et s'en est fini de la sécurité sur les réseaux (pour ne donner qu'une des conséquence de l'égalité de $P$ et de $NP$).

Pas dans P ni NPC ?

Pour ne rien rendre simple, il existe de nombreux problèmes pour lesquels on ne connaît pas d'algorithme polynomiaux mais que l'on arrive pas à démontrer NP-complet. Par exemple le problème suivant :

Par exemple en considérant les 3 graphes ci dessous :

Il est clair de voir que les 2 premiers sont isomorphes ($\sigma(a) = 1$, $\sigma(b) = 2$, $\sigma(c) = 4$ et $\sigma(d) = 3$) alors que le troisième ne l'est pas.

Mais c'est moins clair avec les deux suivants :

Pour vérifier que la deux graphes $G_1 = (V_1, E_1)$ et $G_2 = (V_2, E_2)$ sont isomorphes avec une fonction $\sigma: V_1 \to V_2$ il faut montrer que :

• $\sigma$ est une bijection de $V_1$ dans $V_2$, donc que les deux tableaux $T_1 = [\sigma(x) \mbox{ pour chaque } x \in V_1]$ et $T_2 = [x \mbox{ pour chaque } x \in V_2]$ contiennent les mêmes éléments
• que les arêtes de $V_2$ sont bien arêtes de $V_1$ envoyées via $\sigma$, donc que les deux tableaux $T'_1 = [\{\sigma(x), \sigma(y)\} \mbox{ pour chaque } x \in E_1]$ et $T_2 = [xy \mbox{ pour chaque } xy \in E_2]$ contiennent les mêmes éléments

Ceci peut donc se faire en utilisant deux fois l'algorithme égalité de tableaux avec une complexité totale de $\mathcal{O}(\; |\; E_1\; |^2\; + \; |\; V_1\; |^2\;)$ (en supposant que $\; |\; E_1\; |\; = \; |\; E_2\; |\;$ et $\; |\; V_1\; |\; = \; |\; V_2\; |\;$). On en conclut que :

Le statut du problème de l'isomorphisme de graphe est au statut inconnu : on ne connaît aucun algorithme polynomial pour le résoudre et on n'arrive pas à prouver qu'il est NP-complet.

Même si le statut de l'isomorphie de graphe est inconnue, il est très fortement suspecté qu'il ne soit ni sans P ni dans NPC. Il existe de nombreux autres problèmes dans ce cas là comme le problème de la factorisation (alors que savoir si un nombre est premier ou pas est polynomial. Mais cela dépasse de loin le cadre de ce cours introductif) ou le logarithme discret à la base des algorithmes de chiffrement.

Autres classes

Nous nous restreindrons dans ce cours uniquement aux problèmes de $NP$ (et souvent uniquement à ceux de $P$) mais il en existe une foultitudes d'autres. On peut par exemple citer :

• la classe des problèmes de complexité poly-logarithmique $\mathcal{O}(\log^k(n))$
• la classe des problèmes de complexité polynomial en espace $\mathcal{O}(n^k)$
• ...