Polynominen ja eksponentiaalinen aika
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.:
- lukujoukon järjestäminen (menetelmiä: valintalajittelu O(n2), lomituslajittelu O(n log2 n))
- lyhimpien reittien laskeminen (menetelmä: Floydin algoritmi O(n3)).
Ongelmaluokka P = ”polynomisessa ajassa ratkeavat ongelmat”.