Grafikoni i mrežeAnts

Problem prodavača putovanja je težak, što znači da je to vrlo teško riješiti računalima (barem za veliki broj gradova).

Pronalaženje brzog i točnog algoritma imalo bi ozbiljne implikacije na području računarske znanosti: to bi značilo da postoje brzi algoritmi za svih NP-teških problema. Također bi većinu Internet sigurnosti učinilo beskorisnom, što se oslanja na činjenicu da se vjeruje da su određeni problemi vrlo teški za računala.

Pronalaženje brzog algoritma za rješavanje problema Putničkog prodavača također bi riješilo jedan od najpoznatijih otvorenih problema iz matematike i računarske znanosti, problem P vs NP. To je jedan od sedam problema sa tisućljetnom nagradom, a svaki nosi nagradu u iznosu od milion dolara.