informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-331Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGСЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙШлыкВ А.Институт математики НАН БеларусиBelarus20110504201804(32)1520Copyright © Шлык В.А., 20182018Шлык В.А.Шлык В.А.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/331

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

ReferencesСхрейвер, А. Теория линейного и целочисленного программирования. В 2 т. Т. 2 /Схрейвер, А. Теория линейного и целочисленного программирования. В 2 т. Т. 2 /А. Схрейвер. – М. : Мир, 1991. – 704 с.А. Схрейвер. – М. : Мир, 1991. – 704 с.Grötschel, M. Polyhedral theory / M. Grötschel, M. Padberg // The travelling salesman problem: a guided tour of combinatorial optimization ; ed. E.L. Lawler [et al.]. – Chichester, 1985. – P. 252–305.Grötschel, M. Polyhedral theory / M. Grötschel, M. Padberg // The travelling salesman problem: a guided tour of combinatorial optimization ; ed. E.L. Lawler [et al.]. – Chichester, 1985. – P. 252–305.Шлык, В.А. Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств / В.А. Шлык // Записки научных семинаров ПОМИ. – 2010. – Т. 378. – С. 171–183.Шлык, В.А. Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств / В.А. Шлык // Записки научных семинаров ПОМИ. – 2010. – Т. 378. – С. 171–183.Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 255 с.Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 255 с.Woeginger, G.J. On the equal-subset-sum problem / G.J. Woeginger // Information Processing Letters. – 1992. – Vol. 42. – P. 299–302.Woeginger, G.J. On the equal-subset-sum problem / G.J. Woeginger // Information Processing Letters. – 1992. – Vol. 42. – P. 299–302.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. –Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. –М. : Мир, 1982. – 416 с.М. : Мир, 1982. – 416 с.Рокафеллар, Р. Выпуклый анализ / Р. Рокафеллар. – М. : Мир, 1973. – 469 с.Рокафеллар, Р. Выпуклый анализ / Р. Рокафеллар. – М. : Мир, 1973. – 469 с.Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Доклады НАН Бе-Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Доклады НАН Бе-ларуси. – 2008. – Т. 52, № 3. – С. 5–10.ларуси. – 2008. – Т. 52, № 3. – С. 5–10.

The authors declare that there are no conflicts of interest present.