Задача коммивояжёра считается одной из самых сложных задач комбинаторной оптимизации, потому что относится к классу NP-трудных задач. 12 Это означает, что для её решения в общем виде не существует алгоритма, работающего за полиномиальное время. 1

Кроме того, количество возможных маршрутов в задаче коммивояжёра растёт факториально с увеличением числа городов. 1 Это делает задачу вычислительно сложной даже при относительно небольшом числе городов. 1

Также задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (>66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет. 23