Preview

Информатика

Расширенный поиск

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

Полный текст:

Аннотация

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

Об авторе

В А. Шлык
Институт математики НАН Беларуси
Беларусь


Список литературы

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.


Для цитирования:


Шлык В.А. СЛОЖНОСТЬ ЗАДАЧИ РАСПОЗНАВАНИЯ ОДНОГО КЛАССА РЕШЕНИЙ ЛИНЕЙНЫХ УРАВНЕНИЙ. Информатика. 2011;(4(32)):15-20.

For citation:


. . Informatics. 2011;(4(32)):15-20. (In Russ.)

Просмотров: 63


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)