Антоація. На прикладі задачі про комівояжера розглянуто клас важкорозв’язних задач, які мають поліноміальний алгоритм розв’язання. Доведено, що цьому класу належать задачі, в яких спеціальним чином змодельована структура вхідних даних. Іл.: 1. Бібліогр.: 8 назв.

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