13.5 Les probl` emes NP-complets
445
trois variables, et chacune peut prendre soit la valeur VRAI, soit la valeur FAUX). Par
contre, le probl` eme devient beaucoup plus compliqu´ e lorsqu’on a un grand nombre de
variables. D´ ej` a, `
a 100 variables, l’ordinateur doit tester 2
100 ensembles de valeurs. De
plus, en g´ en´ eral, il n’existe pas de raccourci.
C’est pourquoi ce probl` eme a int´ eress´ e les chercheurs, et un algorithme de solution
par ADN a ´ et´ e propos´ e. En effet, comme tous les probl` emes de v´ erification exhaustive,
celui-ci b´ en´ eficie grandement des capacit´ es de calcul en parall` ele, puisqu’avec l’ADN,
tous les cas sont test´ es en mˆ eme temps. La difficult´ e devient alors d’extraire la bonne
solution, si elle existe.
Au d´ epart, il s’agit de trouver une fa¸ con de g´ en´ erer dans l’´ eprouvette toutes les
assignations de valeurs possibles sous forme de brins d’ADN. Par exemple, si on a trois
variables, il faut trouver une fa¸ con de repr´ esenter chacune des 2
3 = 8 possibilit´ es.
Ceci est possible ` a l’aide de la th´ eorie des graphes. En effet, on mod´ elise les assignations possibles en se servant du graphe de la figure 13.10. Il y a une bijection entre
l’ensemble des chemins de longueur maximale du graphe et l’ensemble des assignations
de valeurs de v´ erit´ e ` a chacune des variables. On note FAUX par 0 et VRAI par 1. Les
sommets a
0
j repr´ esentent la valeur 0 pour x j , et les sommets a
1
j , la valeur 1 pour x j .
Les v i sont simplement des s´ eparateurs. Par exemple, le chemin a
0
1 v 1 a
0
2 v 2 a
0
3 v 3 repr´ esente
l’assignation de la valeur de v´ erit´ e FAUX `
a chacune des trois variables. On peut facilement voir que, en suivant tous les trajets maximaux du graphe, on ´ enum´ erera les huit
assignations diff´ erentes de valeurs pour les trois variables.
Fig. 13.10. Graphe associ´ e ` a l’´ enonc´ e logique α = (x1 ∨ x2) ∧ ¬x3 (et `
a tout ´ enonc´ e ` a trois
variables)
Ceci est utile, car la premi` ere ´ etape de l’algorithme par ADN consiste ` a produire
des exemplaires de chacun des huit chemins possibles pour pouvoir les tester ensuite.
Pour ce faire, l’exp´ erience fournie par la r´ esolution du probl` eme d’Adleman nous sera
tr` es pr´ ecieuse : en effet, nous savons d´ ej` a comment coder les sommets et les arˆ etes
d’un graphe orient´ e pour g´ en´ erer tous les chemins possibles. Nous commencerons par
attribuer `
a chacun des sommets du graphe une s´ equence de 2N bases azot´ ees et ` a
chacune des arˆ etes les compl´ ements des N derni` eres bases azot´ ees du sommet de d´ epart
suivis des compl´ ements des N premi` eres bases du sommet d’arriv´ ee. Le N d´ epend du
445
trois variables, et chacune peut prendre soit la valeur VRAI, soit la valeur FAUX). Par
contre, le probl` eme devient beaucoup plus compliqu´ e lorsqu’on a un grand nombre de
variables. D´ ej` a, `
a 100 variables, l’ordinateur doit tester 2
100 ensembles de valeurs. De
plus, en g´ en´ eral, il n’existe pas de raccourci.
C’est pourquoi ce probl` eme a int´ eress´ e les chercheurs, et un algorithme de solution
par ADN a ´ et´ e propos´ e. En effet, comme tous les probl` emes de v´ erification exhaustive,
celui-ci b´ en´ eficie grandement des capacit´ es de calcul en parall` ele, puisqu’avec l’ADN,
tous les cas sont test´ es en mˆ eme temps. La difficult´ e devient alors d’extraire la bonne
solution, si elle existe.
Au d´ epart, il s’agit de trouver une fa¸ con de g´ en´ erer dans l’´ eprouvette toutes les
assignations de valeurs possibles sous forme de brins d’ADN. Par exemple, si on a trois
variables, il faut trouver une fa¸ con de repr´ esenter chacune des 2
3 = 8 possibilit´ es.
Ceci est possible ` a l’aide de la th´ eorie des graphes. En effet, on mod´ elise les assignations possibles en se servant du graphe de la figure 13.10. Il y a une bijection entre
l’ensemble des chemins de longueur maximale du graphe et l’ensemble des assignations
de valeurs de v´ erit´ e ` a chacune des variables. On note FAUX par 0 et VRAI par 1. Les
sommets a
0
j repr´ esentent la valeur 0 pour x j , et les sommets a
1
j , la valeur 1 pour x j .
Les v i sont simplement des s´ eparateurs. Par exemple, le chemin a
0
1 v 1 a
0
2 v 2 a
0
3 v 3 repr´ esente
l’assignation de la valeur de v´ erit´ e FAUX `
a chacune des trois variables. On peut facilement voir que, en suivant tous les trajets maximaux du graphe, on ´ enum´ erera les huit
assignations diff´ erentes de valeurs pour les trois variables.
Fig. 13.10. Graphe associ´ e ` a l’´ enonc´ e logique α = (x1 ∨ x2) ∧ ¬x3 (et `
a tout ´ enonc´ e ` a trois
variables)
Ceci est utile, car la premi` ere ´ etape de l’algorithme par ADN consiste ` a produire
des exemplaires de chacun des huit chemins possibles pour pouvoir les tester ensuite.
Pour ce faire, l’exp´ erience fournie par la r´ esolution du probl` eme d’Adleman nous sera
tr` es pr´ ecieuse : en effet, nous savons d´ ej` a comment coder les sommets et les arˆ etes
d’un graphe orient´ e pour g´ en´ erer tous les chemins possibles. Nous commencerons par
attribuer `
a chacun des sommets du graphe une s´ equence de 2N bases azot´ ees et ` a
chacune des arˆ etes les compl´ ements des N derni` eres bases azot´ ees du sommet de d´ epart
suivis des compl´ ements des N premi` eres bases du sommet d’arriv´ ee. Le N d´ epend du