哪个是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，否则旅行商问题的时间复杂度更高。