Petite confusion dans l’article de techrepublic et dans l’article wikipedia, qui mentionne le problème du voyageur de commerce comme étant un problème d’optimisation. C’est faux. Le problème du voyageur de commerce est un problème de décision (un problème dont la réponse est oui ou non).
Définition possible (empruntée à l’excellent "complexity zoo") : « Given a set of n cities, and the distance between each pair of cities, is there a route that visits each city exactly once before returning to the starting city, and has length at most T ? »
▻https://complexityzoo.net/Complexity_Zoo:N#np
Alors vous me direz : il y a bien une histoire de longueur à optimiser. Oui et non : répondre au problème ne signifie pas nécessairement exhiber une solution.
Après ça, à chaque problème de décision on peut associer un problème d’énumération permettant d’énumérer les solutions du problème. Et dans le cas du voyageur de commerce, ça nous donne un problème d’optimisation (j’énumère en essayant de converger vers le minima d’une fonction objectif).
Bon et sinon sur ces histoires de quantum computing, c’est vachement intéressant mais pour l’instant on reste un peu sur sa faim. Le jour où on résoudra le problème SAT en un claquement de doigt ça commencera à m’intéresser :o).