RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский журнал чистой и прикладной математики // Архив

Сиб. журн. чист. и прикл. матем., 2018, том 18, выпуск 4, страницы 43–55 (Mi vngu484)

Задача о рюкзаке для групп Баумслага–Солитера

Ф. А. Дудкинab, А. В. Трейерc

a Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск, 630090, Россия
b Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, Новосибирск, 630090, Россия
c Омский государственный технический университет, пр. Мира, 11, Омск, 644050, Россия

Аннотация: В настоящей работе мы исследуем проблему алгоритмической разрешимости групповой версии задачи о рюкзаке для группы Баумслага–Солитера вида $BS(p,q)$. Нами доказано, что задача о рюкзаке разрешима в группе $BS(p,q)$ для взаимно простых натуральных $p > 1$, $q > 1$. Для случаев вида $p=1$, $q \in \mathbb{N}$, нами доказано что задача о рюказаке разрешима в группе $BS(1,q)$, но с некотороым ограничением на входные элементы для задачи. Вопрос разрешимости задачи о рюказке для группы $BS(1,q)$ на всём множестве входов остается открытым.

Ключевые слова: группа Баумслага–Солитера, задача о рюкзаке, разрешимость.

УДК: 512.543

Поступила в редакцию: 06.03.2018

DOI: 10.33048/pam.2018.18.404



© МИАН, 2024