les problèmes uraiment dificiles
Ce rta in s p ro bl è mes de la c lasse NP
concentrent en eux toute la di ffic ulté de
la classe NP, e n ce sens que :
• savo ir e n résoudre un seul e n te mps
po ly no mi al pe rm e ttrait de résoud re
tout pro bl è me NP e n te mps po lynomi al,
• pro u ve r qu ' il es t imp oss ibl e d ' e n
réso udre un seul e n te mps po lyno mi al
pro uvera it définiti veme nt que P ~ NP.
On les appe lle les problèmes NP-complets. Cette notio n fut introduite au début
des années 1970 indé pe ndamme nt par
Leoni d Lev in e n Ru ss ie (a lo rs Uni o n
des républiques soc iali stes sov iéti q ues)
et Stephen Cook a u Ca nada, qui pro uvè re nt c hac un de le ur côté qu ' il ex iste
effect ive me nt des problè mes NP-complets, ce qui est loin d 'être une év ide nce.
Le pro bl è me de la 3-colo ri a bilité est
NP-complet ( ce la fut démo ntré en 1972
par Ri c hard Karp) . En conséque nce, s i
vo us découvrez un algo rithme qui le
résout en temps po lyno mi al, vo us a urez
pro uvé que P = NP. C ' est bi e n sûr la
vo ie la plu s te nt a nt e po ur réso udre
l'éni g me « P =NP ? » . Si vous démontrez qu ' il n'ex iste pas d 'algorithme polynomi al po ur ce pro blè me, vo us aurez
démontré que P ~ NP.
O n connaît des pro bl è mes de déc is io n
do nt o n a dé mo ntré qu ' il s de mandaie nt
un te mps de ca lc ul ex po ne nti e l (pa r
exemple savoir si un programme o u une
mac hine de Turing s'arrê te avant avoir
fa it n é ta pes de ca lcul ). De te ls problè mes appartie nne nt à la c lasse notée
EXP, mais ne sont pas dans NP, ni ne sont
NP-complets. Cependant , ces problè mes
sont plu s rares et , très souve nt e n a lgorithmique , o n to mbe sur des problè mes
POUR LES MATHS
Prol,lème de f,a NJHlftdion épitable
Une suite finie de nombres entiers étant donnée, de taille
n, peut-on la séparer en deux paquets ayant la même
somme?
Exemple : (1, 2, 2, 2, 3, 4, 4).
Réponse :oui,car2 +2 +2+3 = 1 +4 +4.
Les iquatiom quadratiqae8
Trois nombres-entiers a, b et cétant donnés, peut-on trouver deux entiers x et y tels que or + by = c?
Prol,l.ime du Sadolm ginéraHN
Au lieu de considérer des problèmes de Sodoku composés
de neuf carrés de neuf cases regroupés en un grand carré
de neuf lignes et neuf eolonnes, on considère des problèmes
composés de n2 carrés den• cases regroupés en un grand
carré de n"lignes et n2 colonnes avec les mêmes règles de
remplissage. La question poaêeest: un énoncé étant donné,
possède-t-il une solution ?
Le prol,lème . . nlOls erouâ
Une liste finie de mots (un dictionnaire), D, étant donnée,
ainsi qu'une grille de mots croisés de taille n
2 (c'est-à-dire
une grille carrée vide avec quelques cases noircies), peuton remplir la grille de mots croisés en utilisant des mots pris
dansD?
Stephen Arthur Cook
(né en 1939).
Hors-série n ° 52. Mathématiques & informatique Tangente
Ce rta in s p ro bl è mes de la c lasse NP
concentrent en eux toute la di ffic ulté de
la classe NP, e n ce sens que :
• savo ir e n résoudre un seul e n te mps
po ly no mi al pe rm e ttrait de résoud re
tout pro bl è me NP e n te mps po lynomi al,
• pro u ve r qu ' il es t imp oss ibl e d ' e n
réso udre un seul e n te mps po lyno mi al
pro uvera it définiti veme nt que P ~ NP.
On les appe lle les problèmes NP-complets. Cette notio n fut introduite au début
des années 1970 indé pe ndamme nt par
Leoni d Lev in e n Ru ss ie (a lo rs Uni o n
des républiques soc iali stes sov iéti q ues)
et Stephen Cook a u Ca nada, qui pro uvè re nt c hac un de le ur côté qu ' il ex iste
effect ive me nt des problè mes NP-complets, ce qui est loin d 'être une év ide nce.
Le pro bl è me de la 3-colo ri a bilité est
NP-complet ( ce la fut démo ntré en 1972
par Ri c hard Karp) . En conséque nce, s i
vo us découvrez un algo rithme qui le
résout en temps po lyno mi al, vo us a urez
pro uvé que P = NP. C ' est bi e n sûr la
vo ie la plu s te nt a nt e po ur réso udre
l'éni g me « P =NP ? » . Si vous démontrez qu ' il n'ex iste pas d 'algorithme polynomi al po ur ce pro blè me, vo us aurez
démontré que P ~ NP.
O n connaît des pro bl è mes de déc is io n
do nt o n a dé mo ntré qu ' il s de mandaie nt
un te mps de ca lc ul ex po ne nti e l (pa r
exemple savoir si un programme o u une
mac hine de Turing s'arrê te avant avoir
fa it n é ta pes de ca lcul ). De te ls problè mes appartie nne nt à la c lasse notée
EXP, mais ne sont pas dans NP, ni ne sont
NP-complets. Cependant , ces problè mes
sont plu s rares et , très souve nt e n a lgorithmique , o n to mbe sur des problè mes
POUR LES MATHS
Prol,lème de f,a NJHlftdion épitable
Une suite finie de nombres entiers étant donnée, de taille
n, peut-on la séparer en deux paquets ayant la même
somme?
Exemple : (1, 2, 2, 2, 3, 4, 4).
Réponse :oui,car2 +2 +2+3 = 1 +4 +4.
Les iquatiom quadratiqae8
Trois nombres-entiers a, b et cétant donnés, peut-on trouver deux entiers x et y tels que or + by = c?
Prol,l.ime du Sadolm ginéraHN
Au lieu de considérer des problèmes de Sodoku composés
de neuf carrés de neuf cases regroupés en un grand carré
de neuf lignes et neuf eolonnes, on considère des problèmes
composés de n2 carrés den• cases regroupés en un grand
carré de n"lignes et n2 colonnes avec les mêmes règles de
remplissage. La question poaêeest: un énoncé étant donné,
possède-t-il une solution ?
Le prol,lème . . nlOls erouâ
Une liste finie de mots (un dictionnaire), D, étant donnée,
ainsi qu'une grille de mots croisés de taille n
2 (c'est-à-dire
une grille carrée vide avec quelques cases noircies), peuton remplir la grille de mots croisés en utilisant des mots pris
dansD?
Stephen Arthur Cook
(né en 1939).
Hors-série n ° 52. Mathématiques & informatique Tangente