3 ms·
Isn't the traveling salesman optimization problem non-polynomially-verifiable? https://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunder
by Zee2 4y ago
Isn't the traveling salesman optimization problem non-polynomially-verifiable? https://www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/#:~:text=The%20traveling%20salesperson%20decision%20problem%20has%20a%20polynomial-time,a%20connected%20graph%20G%20G%20and%20a%20cost https://www.nomachetejuggling.com/2012/09/14/traveling-sales...
- Jweb_Guru 4y agoThe optimization problem isn't, but neither are the optimization problems for a bunch of other NP-complete problems. The decision problem (where you specify an upper bound cost) is indeed NP-complete.