А. Н. Рыбалов, “Генерические полиномиальные алгоритмы для проблемы о рюкзаке в некоторых матричных полугруппах”, Сиб. электрон. матем. изв., 2023, том 20, выпуск 1,страницы 100

Математическая логика, алгебра и теория чисел

Генерические полиномиальные алгоритмы для проблемы о рюкзаке в некоторых матричных полугруппах

А. Н. Рыбалов

Sobolev Institute of Mathematics, prospekt Koptyuga 4, Novosibirsk, 630090, Russia. Pevtsova 13, Omsk, 644099, Russia

Аннотация: In this paper, we propose generic polynomial algorithms for the knapsack problems over semigroups of non-negative integer matrices of arbitrary order and semigroup of non-negative second-order integer matrices with determinant 1.

Ключевые слова: generic complexity, knapsack problems, integer matrices.

УДК: 510.652

MSC: 11U99

Поступила 5 июля 2022 г., опубликована 19 февраля 2023 г.

DOI: 10.33048/semi.2023.20.009