RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ПОМИ, 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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:147
    Полный текст:38
    Литература:37
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021