180
Recherche opérationnelle
problème : existe-t-il un circuit hamiltonien de valeur totale inférieure à ? Inversement,
si ce dernier algorithme existait alors il suffirait de faire varier pour trouver de façon
polynomiale (ou presque : il faut ajouter à la représentation de la taille du problème dans
l'ordinateur celle de ) l'optimum du problème d'optimisation. Cette équivalence est cela
dit de faible apport pour la résolution concrète des problèmes combinatoires. En
revanche la distinction que nous opérons ainsi permet d'avancer dans l'exploration de la
notion de complexité des problèmes combinatoires.
c) La classe des problèmes NP
On ne dispose pas, on l'a dit, d'algorithme polynomial permettant de résoudre le
problème du voyageur de commerce. Pour autant, on ne sait pas (ou on ne sait pas
encore) si ce problème est polynomial ou non (pour affirmer qu'il n'est pas polynomial, il
faudrait démontrer qu'il ne peut pas exister d'algorithme polynomial le résolvant, ce qui
n'a pas encore été fait). En revanche, supposons que quelqu'un, à la vue du graphe
symbolisant le problème, exhibe un circuit entre les villes et affirme : ce circuit est
hamiltonien. Il n'est pas très difficile de montrer qu'on peut vérifier dans un temps
polynomial s'il a raison ou pas. De même, si, confronté à un programme linéaire en
nombres entiers, on donne des valeurs positives entières aux variables, on peut vérifier
dans un temps polynomial si cette solution '' devinée '' est réalisable ou non.
Les problèmes d'existence pour lesquels existent des algorithmes polynomiaux
permettant de vérifier qu'une solution est satisfaisante sont appelés problèmes NP. Une
autre façon de dire les choses est d'introduire la notion d'algorithme non déterministe : ce
sont des algorithmes qui, en plus des instructions usuelles, comportent des instructions
de choix : si de bons choix sont effectués un problème NP peut être résolu en un temps
polynomial. C'est le cas du voyageur de commerce (j'ajoute des arcs les uns après les
autres de façon à constituer un circuit et si je suis astucieux je peux '' tomber '' sur un
circuit hamiltonien ou mieux sur un circuit hamiltonien qui a une valeur inférieure à k.
De même, je donne des valeurs entières aux variables du programme linéaire, et avec un
peu de chance j'obtiens une solution réalisable, tout cela dans un temps qui est borné par
une fonction polynomiale de la taille du problème).
Attention : NP ne veut pas dire non polynomial. D'ailleurs, il est facile de voir que les
problèmes polynomiaux sont NP. On a donc :
d) Relations d'ordre entre problèmes
Soit deux problèmes
d'existence. On écrira
si les conditions suivantes
sont respectées :
a) Il existe une transformation
qui est telle que toute solution
de
soit
transformée en une solution
b) La fonction est calculable en un temps polynomial
Cela signifie que l'on peut résoudre le problème
en résolvant le problème .
sera
dit faiblement réductible à
Recherche opérationnelle
problème : existe-t-il un circuit hamiltonien de valeur totale inférieure à ? Inversement,
si ce dernier algorithme existait alors il suffirait de faire varier pour trouver de façon
polynomiale (ou presque : il faut ajouter à la représentation de la taille du problème dans
l'ordinateur celle de ) l'optimum du problème d'optimisation. Cette équivalence est cela
dit de faible apport pour la résolution concrète des problèmes combinatoires. En
revanche la distinction que nous opérons ainsi permet d'avancer dans l'exploration de la
notion de complexité des problèmes combinatoires.
c) La classe des problèmes NP
On ne dispose pas, on l'a dit, d'algorithme polynomial permettant de résoudre le
problème du voyageur de commerce. Pour autant, on ne sait pas (ou on ne sait pas
encore) si ce problème est polynomial ou non (pour affirmer qu'il n'est pas polynomial, il
faudrait démontrer qu'il ne peut pas exister d'algorithme polynomial le résolvant, ce qui
n'a pas encore été fait). En revanche, supposons que quelqu'un, à la vue du graphe
symbolisant le problème, exhibe un circuit entre les villes et affirme : ce circuit est
hamiltonien. Il n'est pas très difficile de montrer qu'on peut vérifier dans un temps
polynomial s'il a raison ou pas. De même, si, confronté à un programme linéaire en
nombres entiers, on donne des valeurs positives entières aux variables, on peut vérifier
dans un temps polynomial si cette solution '' devinée '' est réalisable ou non.
Les problèmes d'existence pour lesquels existent des algorithmes polynomiaux
permettant de vérifier qu'une solution est satisfaisante sont appelés problèmes NP. Une
autre façon de dire les choses est d'introduire la notion d'algorithme non déterministe : ce
sont des algorithmes qui, en plus des instructions usuelles, comportent des instructions
de choix : si de bons choix sont effectués un problème NP peut être résolu en un temps
polynomial. C'est le cas du voyageur de commerce (j'ajoute des arcs les uns après les
autres de façon à constituer un circuit et si je suis astucieux je peux '' tomber '' sur un
circuit hamiltonien ou mieux sur un circuit hamiltonien qui a une valeur inférieure à k.
De même, je donne des valeurs entières aux variables du programme linéaire, et avec un
peu de chance j'obtiens une solution réalisable, tout cela dans un temps qui est borné par
une fonction polynomiale de la taille du problème).
Attention : NP ne veut pas dire non polynomial. D'ailleurs, il est facile de voir que les
problèmes polynomiaux sont NP. On a donc :
d) Relations d'ordre entre problèmes
Soit deux problèmes
d'existence. On écrira
si les conditions suivantes
sont respectées :
a) Il existe une transformation
qui est telle que toute solution
de
soit
transformée en une solution
b) La fonction est calculable en un temps polynomial
Cela signifie que l'on peut résoudre le problème
en résolvant le problème .
sera
dit faiblement réductible à