Grafer och nätverkAnts

Problemet med den resande säljaren är NP-hårt , vilket innebär att det är mycket svårt att lösas av datorer (åtminstone för ett stort antal städer).

Att hitta en snabb och exakt algoritm skulle ha allvarliga konsekvenser inom datavetenskapen: det skulle betyda att det finns snabba algoritmer för alla NP-hårda problem. Det skulle också göra det mesta av Internet-säkerhet värdelös, vilket förlitar sig på att vissa problem tros vara mycket svåra för datorer.

Att hitta en snabb algoritm för att lösa Travelling Salesman-problemet skulle också lösa ett av de mest kända öppna problemen inom matematik och datavetenskap, P vs NP- problemet. Det är ett av de sju tusenprisproblemen , var och en har ett pris på 1 miljoner dollar.