СЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ
Abstract
Доказывается NP-полнота задачи распознавания, является ли неотрицательное целочисленное
решение уравнения a1x1 + a2x2 +…+ ak xk = n с натуральными коэффициентами и свободным членом выпуклой комбинацией двух его неотрицательных целочисленных решений. Используется теорема Войгингера об NP-полноте задачи распознавания множеств, содержащих подмножества равного веса.
References
1. Схрейвер, А. Теория линейного и целочисленного программирования. В 2 т. Т. 2 /
2. А. Схрейвер. – М. : Мир, 1991. – 704 с.
3. 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.
4. Шлык, В.А. Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств / В.А. Шлык // Записки научных семинаров ПОМИ. – 2010. – Т. 378. – С. 171–183.
5. Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 255 с.
6. Woeginger, G.J. On the equal-subset-sum problem / G.J. Woeginger // Information Processing Letters. – 1992. – Vol. 42. – P. 299–302.
7. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. –
8. М. : Мир, 1982. – 416 с.
9. Рокафеллар, Р. Выпуклый анализ / Р. Рокафеллар. – М. : Мир, 1973. – 469 с.
10. Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Доклады НАН Бе-
11. ларуси. – 2008. – Т. 52, № 3. – С. 5–10.
Review
For citations:
. Informatics. 2011;(4(32)):15-20. (In Russ.)
Views: 512
Email this article 