13.5 Les probl` emes NP-complets
443
de Turing peut ˆ etre r´ esolu par un syst` eme d’insertion–d´ el´ etion et, potentiellement, par
un ordinateur `
a ADN. Ceci comprend le calcul d’une fonction MT-calculable. Nous
voyons ici toute la puissance th´ eorique de calcul d’un ordinateur `
a ADN.
13.5 Les probl` emes NP-complets
Ici nous serons tr` es brefs, nous contentant de donner des exemples.
Les probl` emes NP-complets constituent une classe de probl` emes tr` es importants
en informatique. Ce sont des probl` emes faciles ` a ´ enoncer, souvent importants dans
les applications, mais difficiles ` a solutionner par ordinateur. La d´ efinition exacte de
probl` eme NP-complet peut se trouver dans [8].
13.5.1 Le probl` eme du chemin hamiltonien
Un premier exemple de probl` eme NP-complet est le probl` eme du chemin hamiltonien
dont nous avons parl´ e plus tˆ ot (voir la section 13.2). Rappelons que le probl` eme consiste
` a trouver, dans un graphe orient´ e, un chemin passant par tous les sommets du graphe
une et une seule fois. On peut imaginer des applications de ce type de probl` eme dans
les transports.
Si on prend le graphe de la figure 13.1, le probl` eme se r´ esout facilement `
a la main. En
effet, la solution est de passer par les sept sommets dans l’ordre suivant : 0, 3, 5, 1, 2, 4, 6.
C’est encore plus simple par un ordinateur : mˆ eme avec un algorithme rudimentaire, le
calcul prend une fraction de seconde.
Qu’est-ce qui en fait un probl` eme « complexe » ? C’est le temps n´ ecessaire pour
arriver ` a une solution si le graphe est « grand ». En effet, le temps d’ex´ ecution des
algorithmes classiques de recherche d’un chemin hamiltonien d´ epend exponentiellement
du nombre de sommets du graphe. Au-del` a d’un certain nombre de sommets, aucun
ordinateur ne peut trouver de solution dans un d´ elai raisonnable. D´ ej` a, ` a 100 sommets,
un ordinateur prend beaucoup trop de temps pour r´ esoudre le probl` eme. Ceci vient du
fait qu’un ordinateur classique fait ses op´ erations s´ equentiellement (l’une ` a la suite de
l’autre). D’o` u l’int´ erˆ et de construire un ordinateur qui effectuerait ses op´ erations en
parall` ele.
Nous avons vu qu’Adleman a pass´ e sept jours en laboratoire pour arriver au mˆ eme
r´ esultat. Quel est alors l’avantage d’utiliser un ordinateur `
a ADN ? Avec l’ADN, on
peut potentiellement faire des milliards d’op´ erations en parall` ele. C’est ce qui fait sa
force, et c’est pourquoi l’ordinateur `
a ADN fascine les chercheurs. Pour le moment,
la partie la plus longue de l’ex´ ecution d’un algorithme par un ordinateur `
a ADN est la
suite d’op´ erations de laboratoire qui doivent ˆ etre effectu´ ees par un ˆ etre humain. Dans la
m´ ethode par ADN propos´ ee par Adleman, le temps de r´ esolution du probl` eme croˆ ıt de
fa¸ con lin´ eaire par rapport `
a la taille du graphe. On s’aper¸ coit cependant qu’en pratique,
Adleman ne pourrait pas traiter un graphe comportant un tr` es grand nombre de sommets, car le nombre de chemins possibles de longueur ≤ N , croˆ ıt, lui, exponentiellement
443
de Turing peut ˆ etre r´ esolu par un syst` eme d’insertion–d´ el´ etion et, potentiellement, par
un ordinateur `
a ADN. Ceci comprend le calcul d’une fonction MT-calculable. Nous
voyons ici toute la puissance th´ eorique de calcul d’un ordinateur `
a ADN.
13.5 Les probl` emes NP-complets
Ici nous serons tr` es brefs, nous contentant de donner des exemples.
Les probl` emes NP-complets constituent une classe de probl` emes tr` es importants
en informatique. Ce sont des probl` emes faciles ` a ´ enoncer, souvent importants dans
les applications, mais difficiles ` a solutionner par ordinateur. La d´ efinition exacte de
probl` eme NP-complet peut se trouver dans [8].
13.5.1 Le probl` eme du chemin hamiltonien
Un premier exemple de probl` eme NP-complet est le probl` eme du chemin hamiltonien
dont nous avons parl´ e plus tˆ ot (voir la section 13.2). Rappelons que le probl` eme consiste
` a trouver, dans un graphe orient´ e, un chemin passant par tous les sommets du graphe
une et une seule fois. On peut imaginer des applications de ce type de probl` eme dans
les transports.
Si on prend le graphe de la figure 13.1, le probl` eme se r´ esout facilement `
a la main. En
effet, la solution est de passer par les sept sommets dans l’ordre suivant : 0, 3, 5, 1, 2, 4, 6.
C’est encore plus simple par un ordinateur : mˆ eme avec un algorithme rudimentaire, le
calcul prend une fraction de seconde.
Qu’est-ce qui en fait un probl` eme « complexe » ? C’est le temps n´ ecessaire pour
arriver ` a une solution si le graphe est « grand ». En effet, le temps d’ex´ ecution des
algorithmes classiques de recherche d’un chemin hamiltonien d´ epend exponentiellement
du nombre de sommets du graphe. Au-del` a d’un certain nombre de sommets, aucun
ordinateur ne peut trouver de solution dans un d´ elai raisonnable. D´ ej` a, ` a 100 sommets,
un ordinateur prend beaucoup trop de temps pour r´ esoudre le probl` eme. Ceci vient du
fait qu’un ordinateur classique fait ses op´ erations s´ equentiellement (l’une ` a la suite de
l’autre). D’o` u l’int´ erˆ et de construire un ordinateur qui effectuerait ses op´ erations en
parall` ele.
Nous avons vu qu’Adleman a pass´ e sept jours en laboratoire pour arriver au mˆ eme
r´ esultat. Quel est alors l’avantage d’utiliser un ordinateur `
a ADN ? Avec l’ADN, on
peut potentiellement faire des milliards d’op´ erations en parall` ele. C’est ce qui fait sa
force, et c’est pourquoi l’ordinateur `
a ADN fascine les chercheurs. Pour le moment,
la partie la plus longue de l’ex´ ecution d’un algorithme par un ordinateur `
a ADN est la
suite d’op´ erations de laboratoire qui doivent ˆ etre effectu´ ees par un ˆ etre humain. Dans la
m´ ethode par ADN propos´ ee par Adleman, le temps de r´ esolution du probl` eme croˆ ıt de
fa¸ con lin´ eaire par rapport `
a la taille du graphe. On s’aper¸ coit cependant qu’en pratique,
Adleman ne pourrait pas traiter un graphe comportant un tr` es grand nombre de sommets, car le nombre de chemins possibles de longueur ≤ N , croˆ ıt, lui, exponentiellement