Como posso verificar uma solução para o problema do vendedor ambulante em tempo polinomial?

Portanto, o problema de decisão do TSP (problema do vendedor ambulante) é NP completo .

Mas não entendo como posso verificar se uma determinada solução para o TSP é de fato ideal no tempo polinomial, já que não há como encontrar a solução ideal no tempo polinomial (o que ocorre porque o problema não está em P)?

Alguma coisa que possa me ajudar a ver que a verificação pode realmente ser feita em tempo polinomial?

Para ser mais preciso, nós não sabemos se TSP está em . É possível que ele pode ser resolvido em tempo polinomial, embora talvez a crença comum é que P ≠ N P . Agora, lembre-se que isso significa para um problema a ser N P -Hard e N P -completo, ver por exemplo a minha resposta aqui . Acredito que sua fonte de confusão decorre das definições: um N P problema -Hard não é necessariamente em N P .$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Como você e a página da Wikipedia vinculados afirmam, o problema de decisão é completo: dados os custos e um número inteiro x , decida se existe um passeio mais barato que x . Uma maneira de ver o problema em N P é ver que, dada uma solução, é fácil verificar em tempo polinomial se a solução é mais barata que x . Como você pode fazer isso? Basta seguir o tour fornecido, registrar seu custo total e finalmente comparar o custo total com x .$\mathsf{NP}$$x$$x$$\mathsf{NP}$$x$$x$

O ponto crucial é que você deve considerar o problema de decisão :

Problema do vendedor ambulante (versão de decisão). Dado um gráfico ponderado G e um custo alvo C , existe um ciclo hamiltoniano em G cujo peso é no máximo C ?

Para uma instância 'sim', o certificado é apenas um ciclo hamiltoniano cujo peso é no máximo C . Se você pudesse resolver esse problema com eficiência, poderia encontrar o custo de um passeio mínimo por pesquisa binária, começando com o peso de toda a rede como um limite superior.

Você provavelmente está pensando no problema de determinar se uma determinada solução para o TSP é a melhor solução. No entanto, não há uma solução polinomial conhecida para isso, o que significa que esse problema é difícil no NP, mas não necessariamente no NP-Completo.

O Problema de Decisão da TSP é, na verdade, determinar se o peso de qualquer solução em um gráfico Gtem o maior custo C(como explicado melhor na resposta de Niel), o que certamente é verificável em tempo polinomial.

$M$$M$ . Nesse caso, deixe a borda para fora e continue. Caso contrário, coloque a borda de volta e continue. Quando você processar todas as bordas, ficará com um ciclo hamiltoniano de peso mínimo.