The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.
Problema a fost demonstrată a fi NP-dificilă (mai precis, este completă pentru clasa de complexitate FPNP), și versiunea ca problemă de decizie („date fiind costurile și un număr x, să se decidă dacă există un ciclu mai ieftin decât x”) este NP-completă.