Bah, y'a le classique : Décomposition en facteurs premiers d'un entier. A priori, c'est exponentiel, mais on n'est pas sur (et on espère, pasque sinon, on peut dire adieu à la crypto telle qu'on la connait aujourd'hui !). Le truc rigolo, c'est que sur un ordinateur quantique (qui n'existe pour l'instant qu'en théorie), c'est polynomial, alors qu'on ne sait pas résoudre le voyageur de commerce en temps polynomial.
Pour le test de primalité, par contre, on ne savait pas si c'était exponentiel ou pas, mais je crois que des indiens ont trouvé un algo polynomial récemment.
Sinon, si tu veux un problème de complexité équivalente au voyageur de commerce, l'autre classique, c'est SAT. (satisfaisabilité d'un ensemble de clauses)
# nombres premiers
Posté par Matthieu Moy (site web personnel) . En réponse au message Complexité d'algorithmes. Évalué à 4.
Pour le test de primalité, par contre, on ne savait pas si c'était exponentiel ou pas, mais je crois que des indiens ont trouvé un algo polynomial récemment.
Sinon, si tu veux un problème de complexité équivalente au voyageur de commerce, l'autre classique, c'est SAT. (satisfaisabilité d'un ensemble de clauses)