Redigerer Handelsreisendeproblemet (avsnitt)

==Kompleksitetsanalyse==
I [[kompleksitetsteori]] tilhører [[avgjørelsesproblem|avgjørelsesversjonen]] av TSP (hvor lengden L er gitt, oppgaven å bestemme om grafen har en runde på høyst L) til klassen av [[NP-komplett]]e problemer. Dermed er det mulig at [[Det beste, verste og gjennomsnittlige tilfelle|beste tilfelle]] [[Tidskompleksitet|kjøretid]] for en hvilken som helst algoritme for TSP øker superpolynomielt (men ikke mer enn eksponentielt) med antall byer.

Avgjørelsesproblemet kan reduseres til spørsmålet om det finnes en [[Hamiltonvei|Hamiltonsyklus]] i grafen ved å la hver kant ha vekten én. I og med at Hamiltonsyklusproblemet er [[NP-hardt]], vil TSP være minst like vanskelig og er dermed også NP-hardt. På en annen side vil man, gitt en bestemt sti, verifisere at denne har en viss vekt og besøker alle noder nøyaktig én gang, hvilket gjør at det (i likhet med Hamiltonsyklusproblemet) er [[NP-komplett]].