”P = NP” -ongelma
Kauppamatkustajan ongelmalle ei tunneta yhtään kaupunkien määrän n suhteen polynomisessa ajassa toimivaa ratkaisumenetelmää.
Tällaisen menetelmän olemassaoloa ei kuitenkaan ole myöskään osattu todistaa mahdottomaksi. Siten on mahdollista, joskin hyvin epäuskottavaa, että olisi TSP Î P.
TSP-ongelma kuuluu tiettyyn suureen ”vaikean tuntuisten” ongelmien ekvivalenssiluokkaan, ns. NP-täydellisiin ongelmiin, joilla on se ominaisuus että ne ovat joko kaikki helppoja (luokassa P) tai kaikki vaikeita (luokan P ulkopuolella).
Tällä hetkellä ei tiedetä, kumpi vaihtoehto on tosi. Tämä on kuuluisa ratkaisematon kysymys, ns. ”P = NP” -ongelma.