Задача коммивояжёра считается важной в теории вычислительной сложности, потому что она относится к числу трансвычислительных. 34 Уже при относительно небольшом числе городов (больше 66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет. 3

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

Также на примере задачи коммивояжёра были разработаны многие современные распространённые методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов. 3