time-complexity - TSP 和 CPP 之间哪个时间复杂度更高？

Question

从时间复杂度的角度来看，旅行商问题和中国邮递员问题有什么区别？我的意思是 TSP 和 CPP 之间哪个时间复杂度更高？

Answer 1

中国邮递员问题可以在多项式时间内解决（https://en.wikipedia.org/wiki/Route_inspection_problem），TSP是NP完全的（https://en.wikipedia.org/wiki/Travelling_salesman_problem）。

因此，除非 P=NP，否则旅行商问题的时间复杂度更高。