

Consequentemente, se descobrirmos como resolver o problema do caixeiro em tempo polinomial, ficaremos sendo capazes de resolver também, em tempo polinomial, uma grande quantidade de outros problemas matemáticos importantes; por outro lado, se um dia alguém provar que é impossível resolver o problema do caixeiro em tempo polinomial no número de cidades, também se terá estabelecido que uma grande quantidade de problemas importantes não tem solução prática.