|
Mathematical logic, algebra and number theory
Generic polynomial algorithms for the knapsack problem in some matrix semigroups
A. N. Rybalov Sobolev Institute of Mathematics, prospekt Koptyuga 4, Novosibirsk, 630090, Russia. Pevtsova 13, Omsk, 644099, Russia
Abstract:
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.
Keywords:
generic complexity, knapsack problems, integer matrices.
Received July 5, 2022, published February 19, 2023
Citation:
A. N. Rybalov, “Generic polynomial algorithms for the knapsack problem in some matrix semigroups”, Sib. Èlektron. Mat. Izv., 20:1 (2023), 100–109
Linking options:
https://www.mathnet.ru/eng/semr1573 https://www.mathnet.ru/eng/semr/v20/i1/p100
|
|