444
13 L’ordinateur ` a ADN
comme N . Lorsque N devient grand, la probabilit´ e que tous les chemins de longueur
≤ N ne soient pas g´ en´ er´ es augmente. Sans parler de la difficult´ e d’isoler la solution qui
repr´ esente une si petite fraction des chemins g´ en´ er´ es ! Il reste donc encore beaucoup de
chemin ` a parcourir avant qu’on puisse exploiter le parall´ elisme de l’ordinateur ` a ADN.
13.5.2 Le probl` eme de la satisfaisabilit´ e
Un autre exemple classique important de probl` eme NP-complet est le probl` eme de
la satisfaisabilit´ e. Ce probl` eme peut se r´ esoudre ` a l’aide de l’ADN, d’une fa¸ con similaire
` a celle qui est utilis´ ee pour solutionner le probl` eme du chemin hamiltonien d’un graphe.
Ceci montre que la m´ ethode utilis´ ee par Adleman n’est pas r´ eserv´ ee au probl` eme du
chemin hamiltonien.
Le probl` eme de la satisfaisabilit´ e concerne des ´ enonc´ es logiques bˆ atis uniquement de
∨ (OU), ∧ (ET) et ¬ (NON) et de variables bool´ eennes x 1 , . . . , x n qui peuvent prendre
les valeurs VRAI ou FAUX. Regardons deux exemples.
Exemple 13.44 Soit α l’´ enonc´ e suivant :
α = (x 1 ∨ x 2 ) ∧ ¬x 3 .
α repr´ esente la valeur de v´ erit´ e totale de l’´ enonc´ e logique suivant les valeurs de v´ erit´ e de
x 1 , x 2 et x 3 . Bien sˆ ur, α sera VRAI ou FAUX selon les valeurs assign´ ees aux variables.
Par exemple, si x 1 , x 2 et x 3 ont la valeur VRAI, la valeur de α sera FAUX.
Peut-on assigner des valeurs de v´ erit´ e ` a x 1 , x 2 et x 3 telles que α ait la valeur VRAI ?
Ici, il est facile de voir que oui. En effet, nous pouvons par exemple assigner la valeur
VRAI ` a x 1 et ` a x 2 et la valeur FAUX ` a x 3 . Nous disons alors qu’on peut v´ erifier
l’´ equation logique α = VRAI ou encore, qu’on peut satisfaire `
a α.
Exemple 13.45 Consid´ erons maintenant l’´ enonc´ e logique :
β = (x 1 ∨ x 2 ) ∧ (¬x 1 ∨ x 2 ) ∧ (¬x 2 ).
Dans ce cas-ci, on peut facilement se convaincre qu’il n’existe pas de valeur de v´ erit´ e
pour x 1 et x 2 permettant de v´ erifier l’´ equation logique β = VRAI. On ne peut donc
satisfaire `
a β.
D´ efinition 13.46 On peut satisfaire ` a un ´ enonc´ e logique compos´ e uniquement de ∨
(OU), de ∧ (ET), de ¬ (NON) et de variables bool´ eennes x 1 , . . . , x n s’il existe une
assignation de valeurs de v´ erit´ e aux variables bool´ eennes pour laquelle l’´ enonc´ e logique
prend la valeur VRAI.
L’exemple 13.44 ´ etait facile `
a visualiser pour un ˆ etre humain et facile `
a programmer,
mˆ eme avec un algorithme rudimentaire. En effet, pour un ordinateur, il s’agit simplement de tester toutes les valeurs possibles (2
3 dans le cas de cet exemple, car il y a
13 L’ordinateur ` a ADN
comme N . Lorsque N devient grand, la probabilit´ e que tous les chemins de longueur
≤ N ne soient pas g´ en´ er´ es augmente. Sans parler de la difficult´ e d’isoler la solution qui
repr´ esente une si petite fraction des chemins g´ en´ er´ es ! Il reste donc encore beaucoup de
chemin ` a parcourir avant qu’on puisse exploiter le parall´ elisme de l’ordinateur ` a ADN.
13.5.2 Le probl` eme de la satisfaisabilit´ e
Un autre exemple classique important de probl` eme NP-complet est le probl` eme de
la satisfaisabilit´ e. Ce probl` eme peut se r´ esoudre ` a l’aide de l’ADN, d’une fa¸ con similaire
` a celle qui est utilis´ ee pour solutionner le probl` eme du chemin hamiltonien d’un graphe.
Ceci montre que la m´ ethode utilis´ ee par Adleman n’est pas r´ eserv´ ee au probl` eme du
chemin hamiltonien.
Le probl` eme de la satisfaisabilit´ e concerne des ´ enonc´ es logiques bˆ atis uniquement de
∨ (OU), ∧ (ET) et ¬ (NON) et de variables bool´ eennes x 1 , . . . , x n qui peuvent prendre
les valeurs VRAI ou FAUX. Regardons deux exemples.
Exemple 13.44 Soit α l’´ enonc´ e suivant :
α = (x 1 ∨ x 2 ) ∧ ¬x 3 .
α repr´ esente la valeur de v´ erit´ e totale de l’´ enonc´ e logique suivant les valeurs de v´ erit´ e de
x 1 , x 2 et x 3 . Bien sˆ ur, α sera VRAI ou FAUX selon les valeurs assign´ ees aux variables.
Par exemple, si x 1 , x 2 et x 3 ont la valeur VRAI, la valeur de α sera FAUX.
Peut-on assigner des valeurs de v´ erit´ e ` a x 1 , x 2 et x 3 telles que α ait la valeur VRAI ?
Ici, il est facile de voir que oui. En effet, nous pouvons par exemple assigner la valeur
VRAI ` a x 1 et ` a x 2 et la valeur FAUX ` a x 3 . Nous disons alors qu’on peut v´ erifier
l’´ equation logique α = VRAI ou encore, qu’on peut satisfaire `
a α.
Exemple 13.45 Consid´ erons maintenant l’´ enonc´ e logique :
β = (x 1 ∨ x 2 ) ∧ (¬x 1 ∨ x 2 ) ∧ (¬x 2 ).
Dans ce cas-ci, on peut facilement se convaincre qu’il n’existe pas de valeur de v´ erit´ e
pour x 1 et x 2 permettant de v´ erifier l’´ equation logique β = VRAI. On ne peut donc
satisfaire `
a β.
D´ efinition 13.46 On peut satisfaire ` a un ´ enonc´ e logique compos´ e uniquement de ∨
(OU), de ∧ (ET), de ¬ (NON) et de variables bool´ eennes x 1 , . . . , x n s’il existe une
assignation de valeurs de v´ erit´ e aux variables bool´ eennes pour laquelle l’´ enonc´ e logique
prend la valeur VRAI.
L’exemple 13.44 ´ etait facile `
a visualiser pour un ˆ etre humain et facile `
a programmer,
mˆ eme avec un algorithme rudimentaire. En effet, pour un ordinateur, il s’agit simplement de tester toutes les valeurs possibles (2
3 dans le cas de cet exemple, car il y a