Информация о статье журнала "Информатика"
Реферат
Полный текст статьи
Полный текст статьи не доступен
Сложность задачи распознавания одного класса решений линейных уравнений' Шлык В. А. 1

  1. Институт математики НАН Беларуси

УДК: 511.344+519.852.2+519.161

Статья поступила: 07.08.2011

Реферат:

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