Аннотация:
В настоящей работе мы исследуем проблему алгоритмической разрешимости групповой версии задачи о рюкзаке для группы Баумслага–Солитера вида BS(p,q)BS(p,q). Нами доказано, что задача о рюкзаке разрешима в группе BS(p,q)BS(p,q) для взаимно простых натуральных p>1p>1, q>1q>1. Для случаев вида p=1p=1, q∈N, нами доказано что задача о рюказаке разрешима в группе BS(1,q), но с некотороым ограничением на входные элементы для задачи. Вопрос разрешимости задачи о рюказке для группы BS(1,q) на всём множестве входов остается открытым.
Ключевые слова:
группа Баумслага–Солитера, задача о рюкзаке, разрешимость.
Поступила в редакцию: 06.03.2018
Тип публикации:
Статья
УДК:512.543
Образец цитирования:
Ф. А. Дудкин, А. В. Трейер, “Задача о рюкзаке для групп Баумслага–Солитера”, Сиб. журн. чист. и прикл. матем., 18:4 (2018), 43–55