|
Зап. научн. сем. ПОМИ, 2010, том 378, страницы 171–183
(Mi znsl3833)
|
|
|
|
Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств
В. А. Шлык Институт математики Национальной Академии наук Беларуси, Минск, Беларусь
Аннотация:
В работе показано, что класс разбиений, не представимых в виде выпуклой комбинации двух разбиений того же числа, совпадает с классом рюкзачных разбиений и с классом мультимножеств Сидона, включающим множества без сумм и стандартные множества Сидона. Доказано, что задача распознавания рюкзачных разбиений co-$NP$-полна и, следовательно, неразрешима за полиномиальное время, если верна гипотеза $P\neq NP$. Библ. – 13 назв.
Ключевые слова:
политопы разбиений чисел, вершины политопов, мультимножества Сидона, задачи распознавания, $NP$-полнота.
Полный текст:
PDF файл (613 kB)
Список литературы:
PDF файл
HTML файл
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2011, 174:1, 90–96
Реферативные базы данных:
Тип публикации:
Статья
УДК:
511.344+511.178+519.852.2+519.161 Поступило: 18.07.2010
Образец цитирования:
В. А. Шлык, “Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств”, Теория представлений, динамические системы, комбинаторные методы. XVIII, Зап. научн. сем. ПОМИ, 378, ПОМИ, СПб., 2010, 171–183; J. Math. Sci. (N. Y.), 174:1 (2011), 90–96
Цитирование в формате AMSBIB
\RBibitem{Shl10}
\by В.~А.~Шлык
\paper Задачи распознавания некоторых классов разбиений чисел и числовых мультимножеств
\inbook Теория представлений, динамические системы, комбинаторные методы.~XVIII
\serial Зап. научн. сем. ПОМИ
\yr 2010
\vol 378
\pages 171--183
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl3833}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2011
\vol 174
\issue 1
\pages 90--96
\crossref{https://doi.org/10.1007/s10958-011-0283-0}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79952814200}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/znsl3833 http://mi.mathnet.ru/rus/znsl/v378/p171
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Просмотров: |
Эта страница: | 146 | Полный текст: | 38 | Литература: | 37 |
|