Ici, les variables que l’on est autorisé à manipuler ne prennent que deux valeurs : Vrai ou Faux. Ce sont des variables booléennes. Ainsi, si x est une telle variable, soit x a pour valeur Vrai (x = Vrai), soit x a pour valeur Faux (x = Faux). Pour élémentaires et restreintes qu’elles soient, ces valeurs permettent tout de même de faire des calculs. Pour cela, on définit des opérations, un peu comme l’addition ou l’inverse pour les nombres ordinaires (non nuls).
Qui fait non, non, non…
La première opération est la négation : si x est une variable ayant une certaine valeur booléenne, alors ¬ x vaut le « contraire » de x, au sens où ¬Vrai = Faux et ¬Faux = Vrai. L’opérateur ¬ se prononce « Non » (donc Non(Vrai) = Faux, ce qui paraît logique !).
Pour définir notre seconde opération, il convient de simplifier un peu le formalisme standard. Une 3-clause est un triplet composé de variables ou de négations de variables. Les variables composant une 3-clause doivent être distinctes, mais l’ordre dans le triplet n’a aucune importance. Voici quelques exemples de 3-clauses avec les variables booléennes x, y, z et t :
(x, y, t),
(z, ¬ x, ¬ t),
(¬ y, ¬ x, ¬ t),
( ¬ z, ¬ t, ¬ y).
La 3-clause (x,¬ y, z) sera pour nous la même que (z, x, ¬ y), car l’ordre dans le triplet n’est pas important.
Les exemples de triplets qui suivent ne seront pas considérés ici comme des 3-clauses :
(x, y, x), car x apparaît deux fois dans le triplet, (x, ¬ x, t), car x apparaît deux fois (une fois sous la forme « positive » x et une fois sous la forme « négative » ¬ x).
Une 3-clause a elle aussi une valeur booléenne : si ses trois composantes ont pour valeur Faux, alors la 3-clause a la valeur Faux. Sinon (c’est-à-dire si au moins une composante du triplet a pour valeur Vrai), elle a la valeur Vrai.
Si une 3-clause a la valeur Vrai, alors on dit qu’elle est satisfaite. Par exemple, si x = Faux,
y = Vrai, z = Vrai et t = Faux, alors les 3-clauses suivantes sont satisfaites :
(¬ x, y, z),
(y, ¬ z, t),
(¬ y, ¬ z, ¬ t),
(x, ¬ z, ¬ t).
En revanche, les 3-clauses suivantes ne sont pas satisfaites (elles reçoivent la valeur Faux):
(x, ¬ z, t),
(x, y, z),
( ¬ x, t, ¬ y).
[encadre]
Ce que comporte une 3-clause
Une 3-clause est décrite ici comme un triplet de variables ou de négations de variables dans lequel l’ordre des trois éléments n’a pas d’importance. En fait, une 3-clause est un « ou » logique (noté ⌄ ) sur ses trois valeurs booléennes. Une 3-clause comme (x,¬ y, z) se lit x ⌄ ¬ y ⌄ z, une expression qui correspond à « x, ou non(y), ou z » (chaque « ou » étant inclusif).
Dans un « ou » logique, l’ordre n’a pas d’importance : « a ou b » a la même valeur de vérité que « b ou a », et la valeur booléenne associée à « a ou b ou c » est Vrai si, et seulement si, au moins l’une des valeurs booléennes a, b ou creçoit la valeur Vrai.
[/encadre]
No SATisfaction…
Le problème central de la satisfaction est le suivant. On se donne n variables booléennes x1, x2… xn ainsi que des 3-clauses, C 1, C 2… Ck, construites avec ces seules variables. Les 3-clauses sont supposées deux à deux distinctes. L’objectif est d’attribuer une valeur booléenne à chaque variable (ce qui s’appelle une affectation) de sorte à maximiser le nombre de nos 3-clauses satisfaites.
Illustrons la question par un exemple afin de se convaincre que ce n’est pas un exercice facile. On se donne n = 7 variables, notées a, b, c, d, e, f et g, ainsi que les cinq 3-clauses suivantes :
C1 = (a, b, ¬ d ),
C2 = (¬ a, ¬ e, f ),
C3 = (e, f , ¬ g),
C4 = (a, c, ¬ d ),
C5 = (c, ¬ d, f ).
L’affectation « a = Faux, b = Faux, c = Faux, d = Vrai, e = Faux, f = Vrai et g = Vrai » permet de satisfaire C2, C3 et C5, mais ni C1, ni C4.
Est-ce qu’une autre affectation permettrait de faire mieux ? En cherchant un peu, on trouve par exemple « a = Vrai, b = Faux, c = Faux, d = Vrai, e = Faux, f = Vrai et g = Vrai », permettant effectivement de faire mieux (en l’occurrence, cette affectation permet de satisfaire toutes les 3-clauses).
Dans le cas général, comment trouver l’affectation maximisant le nombre de 3-clauses satisfaites ? Une première idée, bien entendu, serait tout bonnement d’essayer toutes les affectations possibles et, pour chacune d’elle, de compter le nombre de 3-clauses satisfaites. Après les avoir toutes essayées, il serait possible de dire combien de 3-clauses il est possible de satisfaire au maximum, ainsi que de donner un exemple explicite d’affectation atteignant ce maximum.
Cette tâche naïve peut facilement être décrite par un algorithme, puis exécutée par un programme informatique qui réalisera ce travail fastidieux de façon automatique. Le problème, c’est le temps qu’il faudra pour résoudre le problème de cette manière…
En effet, combien existe-t-il d’affectations possibles pour n variables et k 3-clauses ? Chaque variable peut prendre exactement deux valeurs (Vrai et Faux). Il y a n variables, et donc 222…2 = 2n affectations possibles à tester. Pour chacune de ces 2n affectations, il faut compter le nombre de 3-clauses satisfaites… : on n’en sortira pas si n est un « grand » nombre !
Pour s’en persuader, prenons un exemple concret. Supposons que l’on ait n = 45 variables et que notre machine soit capable de générer et de tester cent affectations chaque seconde. Il faudra alors 2 45 / 100 secondes pour répondre à notre question, ce qui fait plus de onze mille ans ! Vous aurez largement le temps de méditer sur votre façon de concevoir vos algorithmes…
Vous disposez d’une machine qui vous permet de traiter non pas cent mais cent mille affectations par seconde ? Bravo ! Dans ce cas, il ne vous faudra plus que onze années d’attente pour avoir votre réponse…
Autant dire qu’il est temps d’essayer autre chose.
L’affectation maximisant le nombre de 3-clauses satisfaites fait partie de la catégorie des problèmes algorithmiques pour lesquels personne à l’heure actuelle ne connaît de solution « satisfaisante », c’est-à-dire fournissant le résultat optimal (le maximum de 3-clauses satisfaites) en un nombre « raisonnable » de calculs. Sans entrer dans le détail technique de ce qu’il est légitime d’appeler « raisonnable », on se convaincra que l’exemple précédent illustre que le nombre 2n de calculs ne l’est pas. En revanche, n 2 serait considéré comme recevable, tout comme, plus généralement, un polynôme en n. De façon plus technique, la question de la maximisation du nombre de 3-clauses satisfaites est liée au problème de décision appelé 3-SAT, qui est NP-complet.
À l’heure actuelle, personne ne sait résoudre ce problème de manière exacte (trouver exactement le maximum) avec un algorithme de complexité « raisonnable » (par exemple polynomiale en le nombre de variables). De nombreux experts pensent même que ce n’est pas possible. Pour s’en sortir quand même, il va donc falloir ruser.
On va jouer à pile ou face
Pour chaque variable xi du système de 3-clauses, tirons au hasard sa valeur, en jouant à pile ou face avec une pièce non truquée par exemple : si l’on tombe sur pile, alors on pose xi = Vrai, et lorsque l’on obtient face, on pose xi = Faux. Une fois l’affectation ainsi fixée de façon aléatoire, il suffit de compter le nombre de 3-clauses parmi C1, C2… Ck qui sont satisfaites.
Un tel procédé a-t-il une chance d’approcher du maximum cherché ?
Considérons une 3-clause Ci , qui est donc composée de trois variables distinctes (sous forme négative ou positive). Une observation va grandement nous aider : il n’existe qu’une seule affectation rendant une 3-clause Ci non satisfaite. En effet, Ci n’est pas satisfaite si, et seulement si, ses trois composantes ont la valeur Faux.
Par exemple, le seul moyen pour que Ci = (xu, ¬ xv, ¬ xw) ne soit pas satisfaite est que l’on ait xu = Faux, xv = Vrai et xw = Vrai. Toutes les autres combinaisons de valeurs booléennes pour les trois variables xu, xv et xw donnent la valeur Vrai à Ci . Or, il y a exactement 222 = 8 façons d’attribuer des valeurs à xu, xv et xw. En tirant ces valeurs au hasard, on a donc une chance sur huit seulement que Ci ne soit pas satisfaite, c’est-à-dire sept chances sur huit qu’elle soit satisfaite.
Voilà qui est plutôt une bonne nouvelle : en moyenne, on a sept chances sur huit pour qu’une 3-clause soit satisfaite. Avec un petit peu de calculs utilisant la notion d’espérance mathématique, cette remarque permet d’établir que le procédé permet de satisfaire en moyenne au moins sept huitièmes des 3-clauses du système (voir en encadré). On en tire deux enseignements :
• Jouer à pile ou face permet de satisfaire sept huitièmes des 3-clauses en moyenne. Ce n’est bien sûr qu’une moyenne (une espérance mathématique, en fait), mais c’est bien intéressant ;
• Il existe nécessairement une affectation permettant de satisfaire au moins sept huitièmes des clauses (sinon, l’espérance n’aurait pas cette valeur). Ainsi, avec par exemple quatre-vingts 3-clauses, vous savez qu’il existe une affectation qui permet d’en satisfaire au moins soixante-dix… même si le résultat ne vous dit pas comment la trouver à coup sûr.
C’est là un exemple de méthode où le hasard joue un rôle déterminant à notre avantage, pour résoudre un système de k équations booléennes à n variables. Voilà un point de rencontre entre les mathématiques (preuve d’existence d’une solution possédant une certaine qualité) et l’algorithmique (une méthode pour arriver, en moyenne, à ce résultat). C’est ainsi qu’avec une simple pièce de monnaie (ou, de façon plus moderne et rapide, un générateur aléatoire informatique), il est possible de résoudre au moins partiellement un problème algorithmique qui, autrement, serait insurmontable.
[encadre]
Un petit calcul d'espérance
Soit Zi la variable aléatoire prenant la valeur 1 si Ci est satisfaite et 0 sinon. L’espérance de Zi est très simple à exprimer à partir de la définition même d’une espérance mathématique :
E( Zi ) = 1
Par ailleurs, P( Zi =1) = 7/8. Ce qui nous intéresse, ce n’est pas une 3-clause particulière, mais les k 3-clauses (deux à deux distinctes).
Soit Z la variable aléatoire représentant le nombre de 3-clauses satisfaites.
Comme Z = Z1 + Z2 +… + Zk,
on a E(Z) = E( Z1 + Z2 +… + Zk ).
Or, l’espérance d’une somme est la somme des espérances.
On en tire que E( Z ) = E( Z1 ) + E( Z2 ) +… + E( Zk ).
Puisque E( Zi ) = 7/8 pour tout i entre 1 et k, il vient finalement que E(Z) = 7k / 8, ce qui correspond aux sept huitièmes des 3-clauses.
[/encadre]
Lire la suite