Аннотация. На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных.

Ключевые слова: труднорешаемые задачи, полиномиальный алгоритм, NP-полные задачи, задача о коммивояжере, задача о назначениях, разрешимый подкласс задач, комбинаторная оптимизация, матрицы Супника, Кальмансона, Демиденко, Монжа.