Gráficos y RedesAnts

El problema del vendedor ambulante es NP-hard , lo que significa que es muy difícil de resolver con computadoras (al menos para un gran número de ciudades).

Encontrar un algoritmo rápido y exacto tendría serias implicaciones en el campo de la informática: significaría que existen algoritmos rápidos para todos los problemas NP-difíciles. También haría inútil la mayor parte de la seguridad de Internet, lo que se basa en el hecho de que se cree que ciertos problemas son muy difíciles para las computadoras.

Encontrar un algoritmo rápido para resolver el problema del vendedor ambulante también resolvería uno de los problemas abiertos más famosos en matemáticas e informática, el problema P vs NP . Es uno de los siete problemas del Premio del Milenio , cada uno con un premio de $ 1 millón.