SAVOIRS
P est-il égal à NP ?
Q111111s Pflblènles NP-ca•IIIIII
Plusiems milliers de problèmes NP-eomplebttlODtconnus
et on en découvre chaque année de nouveaux. Si '90l18 voulez tenter votre chance pour gagner un million de dollars,
en voici une petite liste.
P, . . . . . . . eümlt IMmdltonfen
Un graphe G, de taille n, étant donné, peut-on suivre les arcs
du graphe de façon à passer par tous les nœuds du graphe,
sans passer deux fois par le même nœud et en revenant au
point de départ?
.ProWàte du 1'0flGf18UP. eonmren,e
Un graphe G, de taille n, étant donné avec un nombre sur
chaque arc indiquant sa longueur, et un nombre M étant
fixé, peut-on trouver un chemin du graphe ayant une longueur totale inférieure à M et passant par tous les nœuds
du graphe?
Problème·~ planaire
Un graphe G, de taille n, étant donné, ainsi qu'un entier k,
peut-on trouver knœuds du grapbeGtels qu'en ne retenant
que ces k nœuds et les arcs qui les relient on obtienne un
graphe planaire (représentable sur un plan sans que deux
arcs se coupent) ?
Problème da emenabla ~
Une famille finie d'ensembles finis F, de taille n, étant donnée, ainsi qu'un nombre 1c, peut-on trouver k ensembles
dans la famille F qui soient disjoints deux à deux ?
Exemple : F = {{a, b, c}, {a. e, c,f, g}, {d. e,f}. {a. c, e, i},
{c,f, i}, {g. h, i}, {b,f, ï}, {j, 1c, l, m}, {b, g, h, i}} avec k = 4.
Réponse : oui, en considérant {a, b, c}, {d, e,j}, {g, h, i},
{j, 1c, l, m}.
la grande question
La ques tio n la plu s fo nd ame nta le de
l' inform atique théorique est ce ll e de
savoir si P =NP. Autre ment dit , ce que
l'on pe ut fa ire en te mps po lyno mi a l
non déterministe quand on a une chance
p ar fa ite (cl asse d es probl è mes NP)
pe ut-il toujours être fait en temps po lyno mi a l par un a lgorithme n ' utili sa nt
ni le hasard , ni le para ll é li s me (c lasse
des pro bl è mes P) ?
Pre uve de son importance , le problème
« P = NP ? » est l' un des sept problèmes
que l' Institut C lay a sélectionnés en l' an
2000 (dont un seul a été résolu à ce jour).
Comme pour les six autres, une somme
d ' un millio n de doll ars atte nd celui ou
ceux qui sauront le résoudre. Certains affament que c'est le plus important des sept
probl è mes , et donc le p lu s important
aujo urd' hui e n mathématiques ! Il est
vrai qu ' il est a priori le seul dont la résolution pourrait avo ir des conséquences
pratiques car des centaines de problèmes
concrets sont concernés . Il est aussi celui
dont la portée philosophique est la plu s
grande: il concerne la nature de ce qu 'est
la recherche de solutions dans un ensemble
ex po ne ntie l de poss ibilités , ce qui est
le problème même de la recherche sc ientifique. Dit en termes simples , la question « P = NP ? » signifie « est-ce que
ce que nous po uvo ns tro uver ra pidement , lorsque nous avons de la chance ,
pe ut être trouvé ra pidement par un ca lcul intelligent ?». Sous forme très brève :
l' inte lli ge nce pe ut-e ll e re mpl acer la
chance?
Une autre fo rmulation encore de ce problème est : tout ce que l 'on peut vérifi er
fac ilement peut-il être découvert fac ilement ? Vérifier qu ' un chemin dans un
gra ph e passe pa r to us les nœ ud s du
graphe sans jamais passer deux fo is par
le mê me nœ ud (che min hamiltonien)
est fac ile, do nc, si P = NP, savo ir s' il
ex iste des che mins hamilto ni ens sera
fac ile (on ne connaît pour l' instant aucun
algorithme e ffi cace qui le permet) .
Tout probl ème de la classe P est également dans la cl asse NP. Apparteni r à la
classe NP n'est donc pas un gage de di ffi culté ! Un te l gage ne s'obtient qu ' en
considérant la classe des problèmes NPcompl ets.
Tangente Hors-série n°52. Mathématiques & informatique
P est-il égal à NP ?
Q111111s Pflblènles NP-ca•IIIIII
Plusiems milliers de problèmes NP-eomplebttlODtconnus
et on en découvre chaque année de nouveaux. Si '90l18 voulez tenter votre chance pour gagner un million de dollars,
en voici une petite liste.
P, . . . . . . . eümlt IMmdltonfen
Un graphe G, de taille n, étant donné, peut-on suivre les arcs
du graphe de façon à passer par tous les nœuds du graphe,
sans passer deux fois par le même nœud et en revenant au
point de départ?
.ProWàte du 1'0flGf18UP. eonmren,e
Un graphe G, de taille n, étant donné avec un nombre sur
chaque arc indiquant sa longueur, et un nombre M étant
fixé, peut-on trouver un chemin du graphe ayant une longueur totale inférieure à M et passant par tous les nœuds
du graphe?
Problème·~ planaire
Un graphe G, de taille n, étant donné, ainsi qu'un entier k,
peut-on trouver knœuds du grapbeGtels qu'en ne retenant
que ces k nœuds et les arcs qui les relient on obtienne un
graphe planaire (représentable sur un plan sans que deux
arcs se coupent) ?
Problème da emenabla ~
Une famille finie d'ensembles finis F, de taille n, étant donnée, ainsi qu'un nombre 1c, peut-on trouver k ensembles
dans la famille F qui soient disjoints deux à deux ?
Exemple : F = {{a, b, c}, {a. e, c,f, g}, {d. e,f}. {a. c, e, i},
{c,f, i}, {g. h, i}, {b,f, ï}, {j, 1c, l, m}, {b, g, h, i}} avec k = 4.
Réponse : oui, en considérant {a, b, c}, {d, e,j}, {g, h, i},
{j, 1c, l, m}.
la grande question
La ques tio n la plu s fo nd ame nta le de
l' inform atique théorique est ce ll e de
savoir si P =NP. Autre ment dit , ce que
l'on pe ut fa ire en te mps po lyno mi a l
non déterministe quand on a une chance
p ar fa ite (cl asse d es probl è mes NP)
pe ut-il toujours être fait en temps po lyno mi a l par un a lgorithme n ' utili sa nt
ni le hasard , ni le para ll é li s me (c lasse
des pro bl è mes P) ?
Pre uve de son importance , le problème
« P = NP ? » est l' un des sept problèmes
que l' Institut C lay a sélectionnés en l' an
2000 (dont un seul a été résolu à ce jour).
Comme pour les six autres, une somme
d ' un millio n de doll ars atte nd celui ou
ceux qui sauront le résoudre. Certains affament que c'est le plus important des sept
probl è mes , et donc le p lu s important
aujo urd' hui e n mathématiques ! Il est
vrai qu ' il est a priori le seul dont la résolution pourrait avo ir des conséquences
pratiques car des centaines de problèmes
concrets sont concernés . Il est aussi celui
dont la portée philosophique est la plu s
grande: il concerne la nature de ce qu 'est
la recherche de solutions dans un ensemble
ex po ne ntie l de poss ibilités , ce qui est
le problème même de la recherche sc ientifique. Dit en termes simples , la question « P = NP ? » signifie « est-ce que
ce que nous po uvo ns tro uver ra pidement , lorsque nous avons de la chance ,
pe ut être trouvé ra pidement par un ca lcul intelligent ?». Sous forme très brève :
l' inte lli ge nce pe ut-e ll e re mpl acer la
chance?
Une autre fo rmulation encore de ce problème est : tout ce que l 'on peut vérifi er
fac ilement peut-il être découvert fac ilement ? Vérifier qu ' un chemin dans un
gra ph e passe pa r to us les nœ ud s du
graphe sans jamais passer deux fo is par
le mê me nœ ud (che min hamiltonien)
est fac ile, do nc, si P = NP, savo ir s' il
ex iste des che mins hamilto ni ens sera
fac ile (on ne connaît pour l' instant aucun
algorithme e ffi cace qui le permet) .
Tout probl ème de la classe P est également dans la cl asse NP. Apparteni r à la
classe NP n'est donc pas un gage de di ffi culté ! Un te l gage ne s'obtient qu ' en
considérant la classe des problèmes NPcompl ets.
Tangente Hors-série n°52. Mathématiques & informatique