Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств

В работе показано, что класс разбиений, не представимых в виде выпуклой комбинации двух разбиений того же числа, совпадает с классом рюкзачных разбиений и с классом мультимножеств Сидона, включающим множества без сумм и стандартные множества Сидона. Доказано, что задача распознавания рюкзачных разбиений co-$NP$-полна и, следовательно, неразрешима за полиномиальное время, если верна гипотеза $P\neq NP$. Библ. – 13 назв.