A existência ou não de um método polinomial para resolver o problema do caixeiro viajante é um dos grandes problemas em aberto da Matemática na medida em que Stephen Cook (1971) e Richard Karp (1972) mostraram que uma grande quantidade de problemas importantes (como é o caso de muitos tipos de problemas de otimização combinatória, o caso do problema da decifração de senhas criptografadas com processos modernos como o DES, etc.) podem ser reduzidos, em tempo polinomial, ao problema do caixeiro.