SAVOIRS
par Jean-Paul Delahaye
le problème fondamental de l'informatique théorique
P est-il égal à nP ?
Le problème découvert par Godel paraissait facile ; pourtant,
il résiste depuis cinquante ans, et on a surtout compris qu'il
ne fallait pas s 'attendre à en trouver rapidement la solution.
De quel problème fondamental s 'agit-il ?
L
es problèmes combinato ires classiques(« savoir si un mot contient
un sous- mot donné »,« savo ir
s i un c he min do nn é est le p lus court
chemin re li ant A et B dans un graphe »,
« savo ir si l'entie r N est un carré parfa it » .. . ) se tra itent parfo is rapide ment ,
ou à l' in verse de mandent bea ucoup de
ca lculs. Les cl asses de comp lex ité défi -
•
ni es en in fo rmatique théorique servent
à les ranger en catégories. C'est étra nge,
ma is on ignore si les de ux princ ipa les
c lasses, P et NP, sont éga les !
La classe P
Savo ir si les nœ uds d ' un graphe donné
ayant n nœ uds sont co lori ables à l' a ide
de de ux couleurs (par exemple bl e u et
ro uge) sans que deux nœ uds liés l'un à
l' autre portent la même couleur est fac ile.
On obtient la ré ponse rapidement par la
méthode sui vante. On cho isit un nœ ud ,
que l'o n co lorie e n rou ge , on co lorie
to us les nœ uds qui lui sont liés en ble u ,
on colorie tous les nœuds liés à un nœud
bl e u e n rouge, et on poursuit ainsi de
proche en proche en alternant les couleurs ; quand il ex iste plusie urs composantes connexes au graphe, on procède
de la même faço n po ur chaque composante. Si l' o n re ncontre une im poss ibilité, c'est qu 'aucun coloriage bicolore n ·est
poss ib le, ca r to us les co lori ages fa it s
après le pre mier sont inév itables . Si on
aboutit , c'est que la ré ponse est oui.
Aucun retour en arrière n' est nécessai re
da ns l' utili sa ti o n de la mé th ode (les
nœuds une fo is co~rés ne changent plus
de dti ule ur) et doncia méthode de colori age prend un « temps» (c 'est-à-di re un
nombre d ' étapes) proportionnel en gros
au nombre de nœuds, n. On dit que le probl ème de la 2-co lori abilité est polynom ia l (o u ap p a rli e nl à la c lass e
polynomiale) .
Certains problèmes de décision Oa réponse
do it être « oui » ou « non ») ne peuve nt
être réso lus qu 'en un nombre d ' étapes
majoré par ,l (ou par toute autre pui ssance de n , n mes urant la taille des données). On con sidère encore que ce sont
des problèmes « effi cacement traitables »
et il s constituent la classe P des problèmes que l'on pe ut résoudre en temps
polynomial.
Bien év idemment , un problème demandant un nombre d 'étapes de l'ordre de
11
4 est plus diffic ile (en un sens) qu ' un
problème demandant un nombre d'étapes
82 Tangente Hors-sé , ~ n° 52. Mathématiques & informatique
par Jean-Paul Delahaye
le problème fondamental de l'informatique théorique
P est-il égal à nP ?
Le problème découvert par Godel paraissait facile ; pourtant,
il résiste depuis cinquante ans, et on a surtout compris qu'il
ne fallait pas s 'attendre à en trouver rapidement la solution.
De quel problème fondamental s 'agit-il ?
L
es problèmes combinato ires classiques(« savoir si un mot contient
un sous- mot donné »,« savo ir
s i un c he min do nn é est le p lus court
chemin re li ant A et B dans un graphe »,
« savo ir si l'entie r N est un carré parfa it » .. . ) se tra itent parfo is rapide ment ,
ou à l' in verse de mandent bea ucoup de
ca lculs. Les cl asses de comp lex ité défi -
•
ni es en in fo rmatique théorique servent
à les ranger en catégories. C'est étra nge,
ma is on ignore si les de ux princ ipa les
c lasses, P et NP, sont éga les !
La classe P
Savo ir si les nœ uds d ' un graphe donné
ayant n nœ uds sont co lori ables à l' a ide
de de ux couleurs (par exemple bl e u et
ro uge) sans que deux nœ uds liés l'un à
l' autre portent la même couleur est fac ile.
On obtient la ré ponse rapidement par la
méthode sui vante. On cho isit un nœ ud ,
que l'o n co lorie e n rou ge , on co lorie
to us les nœ uds qui lui sont liés en ble u ,
on colorie tous les nœuds liés à un nœud
bl e u e n rouge, et on poursuit ainsi de
proche en proche en alternant les couleurs ; quand il ex iste plusie urs composantes connexes au graphe, on procède
de la même faço n po ur chaque composante. Si l' o n re ncontre une im poss ibilité, c'est qu 'aucun coloriage bicolore n ·est
poss ib le, ca r to us les co lori ages fa it s
après le pre mier sont inév itables . Si on
aboutit , c'est que la ré ponse est oui.
Aucun retour en arrière n' est nécessai re
da ns l' utili sa ti o n de la mé th ode (les
nœuds une fo is co~rés ne changent plus
de dti ule ur) et doncia méthode de colori age prend un « temps» (c 'est-à-di re un
nombre d ' étapes) proportionnel en gros
au nombre de nœuds, n. On dit que le probl ème de la 2-co lori abilité est polynom ia l (o u ap p a rli e nl à la c lass e
polynomiale) .
Certains problèmes de décision Oa réponse
do it être « oui » ou « non ») ne peuve nt
être réso lus qu 'en un nombre d ' étapes
majoré par ,l (ou par toute autre pui ssance de n , n mes urant la taille des données). On con sidère encore que ce sont
des problèmes « effi cacement traitables »
et il s constituent la classe P des problèmes que l'on pe ut résoudre en temps
polynomial.
Bien év idemment , un problème demandant un nombre d 'étapes de l'ordre de
11
4 est plus diffic ile (en un sens) qu ' un
problème demandant un nombre d'étapes
82 Tangente Hors-sé , ~ n° 52. Mathématiques & informatique