Как я могу проверить решение проблемы коммивояжера за полиномиальное время?

Таким образом, TSP (задача коммивояжера) проблема решения является NP полной .

Но я не понимаю, как я могу проверить, что данное решение TSP на самом деле является оптимальным за полиномиальное время, учитывая, что нет способа найти оптимальное решение за полиномиальное время (потому что проблема не в P)?

Что-нибудь, что могло бы помочь мне понять, что проверка на самом деле может быть сделана за полиномиальное время?

Чтобы быть более точным, мы не знаем, находится ли TSP в . Вполне возможно, что это можно решить за полиномиальное время, хотя, возможно, распространено мнение, что . Теперь вспомните, что значит для проблемы быть -hard и -complete, см., Например, мой ответ здесь . Я полагаю, что ваш источник путаницы проистекает из определений: проблема -hard не обязательно находится в .P ≠ N P N P N $\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$Н $\mathsf{NP}$$\mathsf{NP}$

Как и на странице Википедии вы связываете государства, то проблема решения является -полное: учитывая затраты и целое число , решить , есть ли тур дешевле , чем . Один из способов увидеть проблему в - увидеть, что при заданном решении легко за полиномиальное время проверить, дешевле ли решение, чем . Как ты можешь это сделать? Просто следуйте приведенному туру, запишите его общую стоимость и, наконец, сравните общую стоимость с .х х Н П х $\mathsf{NP}$$x$$x$$\mathsf{NP}$$x$$x$

Суть в том, что нужно учитывать решение проблемы:

Задача коммивояжера (вариант решения). Учитывая взвешенный граф G и целевую стоимость C , существует ли гамильтонов цикл в G , вес которого не больше C ?

Для экземпляра «да», сертификат лишь некоторые гамильтонов цикл, вес которого составляет не более C . Если бы вы могли эффективно решить эту проблему, вы могли бы найти стоимость минимального тура с помощью бинарного поиска, начиная с веса всей сети в качестве верхней границы.

Вы, вероятно, думаете о проблеме определения того, является ли данное решение TSP лучшим решением. Однако для этого не существует известного полиномиального решения, что означает, что эта проблема находится в NP-трудной, но не обязательно NP-полной.

Задача принятия решения TSP на самом деле заключается в определении того, является ли вес любого решения на графике Gмаксимально затратным C(как лучше объяснено в ответе Нила), что, безусловно, можно проверить за полиномиальное время.

$M$$M$