Perusvaikeus TSP-ongelmassa (ja muissa samantapaisissa tehtävissä) on tutkittavien ratkaisuvaihtoehtojen (reittien) määrän n! » nn eksponentiaalinen kasvu (”kombinatorinen räjähdys”):
jos ratkaisuvaihtoehtojen määrä kasvaa vain polynomisesti, m £ nk jollakin k, konetehonkin kasvattaminen auttaa: 10 kertaa aiempaa tehok-kaammalla koneella pystytään ratkomaan 101/k kertaa aiempaa suurempia ongelman tapauksia
jos ratkaisuvaihtoehtojen määrä kasvaa eksponen-tiaalisesti, m ³ cn jollakin c > 1, konetehon lisää-minen ei auta: tehon 10-kertaistaminen kasvattaa ratkaistavien tapausten kokoa enintään vakiolla logc 10.
”Käytännössä ratkeavina” pidetään ongelmia, joilla on jokin syötteen koon n suhteen polynomisessa ajassa toimiva ratkaisumenetelmä, esim.: