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，否则旅行推销员问题具有更高的时间复杂度。