Том 16, номер 6, 2009 г., Стр. 68-73

УДК 519.2+621.391
А. В. Пяткин
О сложности задачи выбора подмножества векторов максимальной суммарной длины

Аннотация:
Рассматривается задача выбора подмножества векторов максимальной суммарной длины. В случае фиксированной размерности пространства эта задача является полиномиально разрешимой. Доказана NP-полнота задачи при нефиксированной размерности пространства.
Библиогр. 6.

Ключевые слова: cуммирование векторов, сложность, NP-полнота.

Пяткин Артём Валерьевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: artem@math.nsc.ru

Статья поступила 4 августа 2009 г.