Измерение NP-трудности задач дискретной оптимизации с помощью оценки структуры декомпозиции

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