Grafi e retiAnts

Il problema del commesso viaggiatore è NP-difficile, il che significa che è molto difficile risolverlo con i computer (almeno per un gran numero di città).

Trovare un algoritmo veloce ed esatto avrebbe serie implicazioni nel campo dell'informatica: significherebbe trovare algoritmi veloci per tutti i problemi NP-difficili. Inoltre renderebbe inutile la maggior parte della sicurezza di Internet, che si basa sul fatto che alcuni problemi sono ritenuti molto difficili per i computer.

Trovare un algoritmo veloce per risolvere il problema del commesso viaggiatore risolverebbe anche uno dei più noti problemi irrisolti in matematica e informatica, il problema P vs NP. È uno dei sette Problemi per il Millennio, la cui soluzione verrà ricompensato con un premio da 1 milione di dollari.