Почему задача коммивояжера считается важной задачей в теории вычислительной сложности?

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

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

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