СЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ

Аннотация

Доказывается NP-полнота задачи распознавания, является ли неотрицательное целочисленное
решение уравнения a1x1 + a2x2 +…+ ak xk = n с натуральными коэффициентами и свободным членом выпуклой комбинацией двух его неотрицательных целочисленных решений. Используется теорема Войгингера об NP-полноте задачи распознавания множеств, содержащих подмножества равного веса.