Le voyageur de commerce 187
décisions (8 fois plus que pour 10 villes). Un tel algorithme est appelé un algorithme exponentiel. Le Saint Graal de ces « problèmes d’optimisation combinatoire »
consiste à trouver un algorithme qui dépend non pas de la n
ème puissance de 2, mais
d’une puissance de n fixe. Plus la puissance est faible, mieux c’est ; si l’algorithme
variait selon n
2 par exemple, dans le cas des 13 villes, il n’y aurait plus que 169 décisions, autrement dit, moins de deux fois le temps nécessaire pour 10 villes. On dit
qu’un tel algorithme est un algorithme polynomial, et les problèmes résolus de cette
manière sont des « problèmes rapides » dont la résolution peut prendre 3 minutes
et non pas des siècles.
Ce genre de problèmes qui peuvent être résolus par ordinateur en temps polynomial
est désigné par la lettre P. On ne sait pas si le problème du voyageur de commerce en
fait partie. Personne n’a réussi à produire un algorithme de temps polynomial pour
le résoudre, mais personne n’a réussi non plus à montrer qu’il n’en n’existe pas.
Une catégorie plus large notée NP est constituée de problèmes dont les solutions
peuvent être vérifiées en temps polynomial. Le problème du voyageur de commerce
en fait certainement partie parce que vérifier qu’un trajet donné est plus court en
distance que n’importe quel autre trajet donné peut se faire en temps polynomial.
Il vous suffit de faire la somme des distances le long dudit trajet et de comparer le
résultat avec le nombre donné. Trouver et vérifier sont deux opérations différentes :
il est par exemple facile de vérifier que 167 × 241 = 40 247 mais trouver les facteurs
de 40 247 est une tout autre affaire.
Tout problème vérifiable en temps polynomial (NP) peut-il être résolu en temps
polynomial (P) ? Si c’était vrai, les deux catégories P et NP seraient identiques et
nous pourrions écrire P = NP. Savoir si P = NP est actuellement un problème ouvert,
et donc délicat, pour les informaticiens. Plus de la moitié de la profession pense que
ce n’est pas vrai : ils croient qu’il existe quelque part des problèmes qui peuvent être
vérifiés en temps polynomial mais qui ne peuvent pas être résolus en temps polynomial. C’est un problème tellement difficile que l’Institut Mathématique Clay a offert
un prix d’un million de dollars pour prouver que P = NP ou P ∙ NP.
l’idée clé
Trouver le meilleur trajet
décisions (8 fois plus que pour 10 villes). Un tel algorithme est appelé un algorithme exponentiel. Le Saint Graal de ces « problèmes d’optimisation combinatoire »
consiste à trouver un algorithme qui dépend non pas de la n
ème puissance de 2, mais
d’une puissance de n fixe. Plus la puissance est faible, mieux c’est ; si l’algorithme
variait selon n
2 par exemple, dans le cas des 13 villes, il n’y aurait plus que 169 décisions, autrement dit, moins de deux fois le temps nécessaire pour 10 villes. On dit
qu’un tel algorithme est un algorithme polynomial, et les problèmes résolus de cette
manière sont des « problèmes rapides » dont la résolution peut prendre 3 minutes
et non pas des siècles.
Ce genre de problèmes qui peuvent être résolus par ordinateur en temps polynomial
est désigné par la lettre P. On ne sait pas si le problème du voyageur de commerce en
fait partie. Personne n’a réussi à produire un algorithme de temps polynomial pour
le résoudre, mais personne n’a réussi non plus à montrer qu’il n’en n’existe pas.
Une catégorie plus large notée NP est constituée de problèmes dont les solutions
peuvent être vérifiées en temps polynomial. Le problème du voyageur de commerce
en fait certainement partie parce que vérifier qu’un trajet donné est plus court en
distance que n’importe quel autre trajet donné peut se faire en temps polynomial.
Il vous suffit de faire la somme des distances le long dudit trajet et de comparer le
résultat avec le nombre donné. Trouver et vérifier sont deux opérations différentes :
il est par exemple facile de vérifier que 167 × 241 = 40 247 mais trouver les facteurs
de 40 247 est une tout autre affaire.
Tout problème vérifiable en temps polynomial (NP) peut-il être résolu en temps
polynomial (P) ? Si c’était vrai, les deux catégories P et NP seraient identiques et
nous pourrions écrire P = NP. Savoir si P = NP est actuellement un problème ouvert,
et donc délicat, pour les informaticiens. Plus de la moitié de la profession pense que
ce n’est pas vrai : ils croient qu’il existe quelque part des problèmes qui peuvent être
vérifiés en temps polynomial mais qui ne peuvent pas être résolus en temps polynomial. C’est un problème tellement difficile que l’Institut Mathématique Clay a offert
un prix d’un million de dollars pour prouver que P = NP ou P ∙ NP.
l’idée clé
Trouver le meilleur trajet