Jak mogę zweryfikować rozwiązanie problemu Traveling Salesman w czasie wielomianowym?

Tak więc problem decyzyjny TSP (problem sprzedawcy podróży) jest NP kompletny .

Ale nie rozumiem, w jaki sposób mogę sprawdzić, czy dane rozwiązanie TSP jest w rzeczywistości optymalne w czasie wielomianowym, biorąc pod uwagę, że nie ma sposobu na znalezienie optymalnego rozwiązania w czasie wielomianowym (co jest spowodowane tym, że problem nie występuje w P)?

Coś, co mogłoby mi pomóc zobaczyć, że weryfikacja może być faktycznie wykonana w czasie wielomianowym?

Mówiąc ściślej, nie wiemy, czy TSP jest w . Możliwe, że da się to rozwiązać w czasie wielomianowym, chociaż być może powszechne jest przekonanie, że . Przypomnijmy teraz, co to znaczy, że problemem jest -hard i -complete, patrz na przykład moja odpowiedź tutaj . Wierzę, że twoje źródło zamieszania wynika z definicji: problem trudny problem niekoniecznie występuje w .P ≠ N P N P N $\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$N $\mathsf{NP}$$\mathsf{NP}$

Jak podajesz ty i strona w Wikipedii, którą łączysz, problem decyzyjny jest kompletny: biorąc pod uwagę koszty i liczbę całkowitą , zdecyduj, czy wycieczka jest tańsza niż . Jednym ze sposobów dostrzeżenia problemu jest to, że polega na tym, że biorąc pod uwagę rozwiązanie, łatwo jest sprawdzić w czasie wielomianowym, czy rozwiązanie jest tańsze niż . Jak możesz to robić? Wystarczy postępować zgodnie z podaną trasą, zapisać całkowity koszt i ostatecznie porównać całkowity koszt do .x x N P x $\mathsf{NP}$$x$$x$$\mathsf{NP}$$x$$x$

Chodzi o to, że musisz wziąć pod uwagę problem decyzyjny :

Problem podróżującego sprzedawcy (wersja decyzyjna). Biorąc pod uwagę wykres ważony G i koszt docelowy C , czy istnieje cykl hamiltonowski w G, którego waga wynosi co najwyżej C ?

Na „tak” przykład, świadectwo to tylko niektóre cykl Hamiltona, którego waga wynosi co najwyżej C . Jeśli potrafisz skutecznie rozwiązać ten problem, możesz znaleźć koszt minimalnej wycieczki za pomocą wyszukiwania binarnego, zaczynając od ciężaru całej sieci jako górnej granicy.

Prawdopodobnie myślisz o problemie ustalenia, czy dane rozwiązanie TSP jest najlepszym rozwiązaniem. Jednak nie ma znanego rozwiązania wielomianowego, co oznacza, że ​​problem ten jest trudny w NP, ale niekoniecznie NP-Complete.

Problem decyzyjny TSP polega w rzeczywistości na określeniu, czy waga dowolnego rozwiązania na wykresie Gjest najbardziej kosztowna C(jak wyjaśniono lepiej w odpowiedzi Niel), co z pewnością można zweryfikować w czasie wielomianowym.

$M$$M$