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

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

Разработанный алгоритм приведения исследуется на точность получения результата исходной
NP-полной задачи и вычислительную сложность. В работе математически доказывается, что алгоритм приведения не снижает точность получения решения двухуровневой кооперативной задачи о назначениях при точном решении задачи коммивояжера. На сами задачи не накладывается никаких ограничительных условий. Также приведено математическое доказательство полиномиальной вычислительной сложности разработанного алгоритма приведения.

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

В работе описаны дальнейшие перспективы по исследованию данного направления.