Comment puis-je vérifier une solution au problème du voyageur de commerce en temps polynomial?

Ainsi, le problème de décision TSP (Traveling salesman problem) est NP complet .

Mais je ne comprends pas comment je peux vérifier qu'une solution donnée à TSP est en fait optimale en temps polynomial, étant donné qu'il n'y a aucun moyen de trouver la solution optimale en temps polynomial (car le problème n'est pas en P)?

Quelque chose qui pourrait m'aider à voir que la vérification peut en fait être effectuée en temps polynomial?

Pour être plus précis, nous ne pas savoir si TSP est en . Il est possible qu'il peut être résolu en temps polynomial, même si peut - être la croyance commune est que P ≠ N P . Maintenant, rappelez-vous ce que cela signifie pour un problème d'être N P -hard et N P -complete, voir par exemple ma réponse ici . Je crois que votre source de confusion découle des définitions: un N P problème de n'est pas nécessairement dans N P .$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Comme vous et la page Wikipedia que vous liez, le problème de décision est complet: étant donné les coûts et un nombre entier x , décidez s'il y a une visite moins chère que x . Une façon de voir le problème dans N P est de voir que, étant donné une solution, il est facile de vérifier en temps polynomial si la solution est moins chère que x . Comment pouvez-vous faire cela? Suivez simplement la visite donnée, enregistrez son coût total et enfin comparez le coût total à x .$\mathsf{NP}$$x$$x$$\mathsf{NP}$$x$$x$

Le nœud est que vous devez considérer le problème de décision :

Problème de voyageur de commerce (version de décision). Étant donné un graphe pondéré G et un coût cible C , existe-t-il un cycle hamiltonien dans G dont le poids est au plus C ?

Pour une instance « oui », le certificat est juste un certain cycle de hamiltonien dont le poids est au plus C . Si vous pouviez résoudre ce problème efficacement, vous pourriez trouver le coût d'une visite minimale par recherche binaire, en commençant par le poids de l'ensemble du réseau comme limite supérieure.

Vous pensez probablement au problème de déterminer si une solution donnée au TSP est la meilleure solution. Cependant, il n'y a pas de solution polynomiale connue pour cela, ce qui signifie que ce problème est en NP-dur, mais pas nécessairement NP-complet.

Le problème de décision du TSP consiste en fait à déterminer si le poids d'une solution dans un graphique Gest le plus cher C(comme mieux expliqué dans la réponse de Niel), ce qui est certainement vérifiable en temps polynomial.

$M$$M$