"Записки научных семинаров ПОМИ"
Том 378, стр. 171-183
Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств
В. А. Шлык
Институт математики
Национальной Академии наук Беларуси,
Сурганова 11,
220072 Минск, Беларусь
v.shlyk@gmail.com
- Аннотация: В работе показано, что класс разбиений, не представимых в виде выпуклой
комбинации двух разбиений того же числа, совпадает с классом рюкзачных
разбиений и с классом мультимножеств Сидона, включающим множества без
сумм, и стандартные множества Сидона. Доказано, что задача распознавания
рюкзачных разбиений co-$NP$-полна и, следовательно, неразрешима за
полиномиальное время, если верна гипотеза $P\neq NP$.
Библ. -- 13 назв.
- Ключевые слова: политопы разбиений чисел, вершины политопов, мультимножества Сидона,
задачи распознавания, $NP$-полнота [polytopes of partitions of numbers, vertices of polytopes,
Sidon multisets, decision problems, NP-completeness]
Полный текст(.pdf)