paragraph_text: Ovo smješta problem trgovačkog putnika u klasu složenosti FP <sup>NP</sup> (klasa funkcijskih problema koji mogu biti riješeni u polinomnom vremenu na determinističkom Turingovom stroju s proročištem za problem u NP), i ustvari je potpun za tu klasu.