de l'ordre de 11
2 . Cependant , pour une première analyse, on les considère tous les
de ux comme re lati vement fac iles . Vo ic i
que lques exemples de problèmes de la
classe de complex ité P :
• Savoir si une suite de 11 entiers est ra ngée en ordre cro issant.
• Savoir si un entier de 11 chi ffres est un
carré parfa it.
• Savoir si un entier de 11 chiffres est un
no mbre premier (probl ème de la primalité: c'est seulement en 2002 que
l'on a pro uvé qu ' il est dans P).
• Savo ir si un mot contient un sous-mot
donné.
Savo ir si les nœuds un graphe possédant 11 nœuds sont colo ri ables à l'aide
de tro is couleurs (par exempl e : ble u,
rouge, jaune) sans que deux nœuds liés
l' un à l'autre portent la même couleur
est plus di ffic ile qu 'avec deux couleurs.
On ne conn aît aucune méthode pol yno mi a le (c'es t-à-dire de ma nd a nt un
te mps de ca lcul maforé par un po lynôme de la vari able 11) conduisant , de
manière certa ine, soit à la répo nse oui ,
so it à la répo nse no n . On soupço nne
qu' il n'ex iste pas de tel algorithme polynomial pour ce problème, mais on ne sait
pas le prouver.
En revanche, il n'y a aucune diffi culté
à co lorer les 11 nœ uds selon une règ le
a rbit ra ire, pui s à exa min e r s i ce la
convie nt. Si vous avez de la chance,
vo us trouverez une solution dès le premier essai et ce sera fini . Sino n vous
recommencerez . li y a 3
11 te ntati ves à
fa ire (car il y a 11 nœ uds po uvant chacun prendre troi s couleurs di ffé rentes).
Lorsque vous les aurez toutes essayées
en utili sant un procédé d 'énumération
systématique , so it vous aurez trou vé
une solution (vous saurez que la réponse
est « oui , le graphe est 3-colori abl e » ),
soit vous n'en aurez pas trouvé (et vo us
POUR LES MATHS
sa urez qu e la ré po nse es t « no n , le
graphe n 'est pas 3-colo ri abl e »).
S i vo us ê tes co mme Go ntra n , le pe rsonnage de Wa lt Di sney à qui le hasard
est toujours favora ble, alors la méthode
« essayer une foi s au ha ard et vérifier »
est parfaite. Cette méthode vous donne
la répo nse e n un te mps propo rtionne l
en gros à 11 . Si vous n'êtes pas Gontra n,
mais que vo us di sposez d ' un ordinateur
parallè le au parallé li sme illimité, vo us
vous e n sorti rez auss i en un nombre
d'étapes en gros proportionnel à n car vous
lancerez 3
11 te ntati ves en parall è le e t
donc saurez, aussi rapidement que Gontran, si le graphe est 3-coloriable ou pas .
On dit que le problème de la 3-coloriablité est un problè me de la classe NP
(pour non déterministe, polynomial) car,
en ayant une chance parfaite et en menant
un essai de manière non déterministe, ou
si l' on di spose d ' un ordinateur au parallélisme illimité, on le résout en temps polyno mial . On ne sait pas, par contre, si ce
problème est dans la c lasse P, car les
seul s algorithmes"étermini stes (et non
parallè les) que l'on connaît sont du type
de celui décrit précédemment , qui procèdent par énumération et demandent
un te mps de travail expo ne ntie l à un
ordinateur non parallèle (ici 3
11 essai s).
D ' une manière généra le, on définit la
c lasse NP comme la c lasse des problèmes de décision (la réponse est « oui »
ou « non ») que l' on sait résoudre e n
temps poly nomial si on a une chance
parfa ite : on utili se un algorithme dont
le nombre d 'étapes est majoré par un
polynôme de la variable n (la taille du
problème), qui fait des choix au hasard ,
et qui vérifie (une foi s que les cho ix
ont été fa its) que c'est bo n . Ce la est
équivalent à utiliser un algorithme lançant des calcul s en parallè le (sans limi -
tation), chacun d'eux ne travaillant qu ' un
no mbre d 'étapes majoré par un mê me
po lynô me de la variable n.
Hors-série n ° 52. Mathématiques & informatique Tangente
2 . Cependant , pour une première analyse, on les considère tous les
de ux comme re lati vement fac iles . Vo ic i
que lques exemples de problèmes de la
classe de complex ité P :
• Savoir si une suite de 11 entiers est ra ngée en ordre cro issant.
• Savoir si un entier de 11 chi ffres est un
carré parfa it.
• Savoir si un entier de 11 chiffres est un
no mbre premier (probl ème de la primalité: c'est seulement en 2002 que
l'on a pro uvé qu ' il est dans P).
• Savo ir si un mot contient un sous-mot
donné.
Savo ir si les nœuds un graphe possédant 11 nœuds sont colo ri ables à l'aide
de tro is couleurs (par exempl e : ble u,
rouge, jaune) sans que deux nœuds liés
l' un à l'autre portent la même couleur
est plus di ffic ile qu 'avec deux couleurs.
On ne conn aît aucune méthode pol yno mi a le (c'es t-à-dire de ma nd a nt un
te mps de ca lcul maforé par un po lynôme de la vari able 11) conduisant , de
manière certa ine, soit à la répo nse oui ,
so it à la répo nse no n . On soupço nne
qu' il n'ex iste pas de tel algorithme polynomial pour ce problème, mais on ne sait
pas le prouver.
En revanche, il n'y a aucune diffi culté
à co lorer les 11 nœ uds selon une règ le
a rbit ra ire, pui s à exa min e r s i ce la
convie nt. Si vous avez de la chance,
vo us trouverez une solution dès le premier essai et ce sera fini . Sino n vous
recommencerez . li y a 3
11 te ntati ves à
fa ire (car il y a 11 nœ uds po uvant chacun prendre troi s couleurs di ffé rentes).
Lorsque vous les aurez toutes essayées
en utili sant un procédé d 'énumération
systématique , so it vous aurez trou vé
une solution (vous saurez que la réponse
est « oui , le graphe est 3-colori abl e » ),
soit vous n'en aurez pas trouvé (et vo us
POUR LES MATHS
sa urez qu e la ré po nse es t « no n , le
graphe n 'est pas 3-colo ri abl e »).
S i vo us ê tes co mme Go ntra n , le pe rsonnage de Wa lt Di sney à qui le hasard
est toujours favora ble, alors la méthode
« essayer une foi s au ha ard et vérifier »
est parfaite. Cette méthode vous donne
la répo nse e n un te mps propo rtionne l
en gros à 11 . Si vous n'êtes pas Gontra n,
mais que vo us di sposez d ' un ordinateur
parallè le au parallé li sme illimité, vo us
vous e n sorti rez auss i en un nombre
d'étapes en gros proportionnel à n car vous
lancerez 3
11 te ntati ves en parall è le e t
donc saurez, aussi rapidement que Gontran, si le graphe est 3-coloriable ou pas .
On dit que le problème de la 3-coloriablité est un problè me de la classe NP
(pour non déterministe, polynomial) car,
en ayant une chance parfaite et en menant
un essai de manière non déterministe, ou
si l' on di spose d ' un ordinateur au parallélisme illimité, on le résout en temps polyno mial . On ne sait pas, par contre, si ce
problème est dans la c lasse P, car les
seul s algorithmes"étermini stes (et non
parallè les) que l'on connaît sont du type
de celui décrit précédemment , qui procèdent par énumération et demandent
un te mps de travail expo ne ntie l à un
ordinateur non parallèle (ici 3
11 essai s).
D ' une manière généra le, on définit la
c lasse NP comme la c lasse des problèmes de décision (la réponse est « oui »
ou « non ») que l' on sait résoudre e n
temps poly nomial si on a une chance
parfa ite : on utili se un algorithme dont
le nombre d 'étapes est majoré par un
polynôme de la variable n (la taille du
problème), qui fait des choix au hasard ,
et qui vérifie (une foi s que les cho ix
ont été fa its) que c'est bo n . Ce la est
équivalent à utiliser un algorithme lançant des calcul s en parallè le (sans limi -
tation), chacun d'eux ne travaillant qu ' un
no mbre d 'étapes majoré par un mê me
po lynô me de la variable n.
Hors-série n ° 52. Mathématiques & informatique Tangente