RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive
Sib. Èlektron. Mat. Izv., 2023 Volume 20, Issue 1, Pages 100–109 (Mi semr1573)
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.

UDC: 510.652

MSC: 11U99

Received July 5, 2022, published February 19, 2023

DOI: 10.33048/semi.2023.20.009


© Steklov Math. Inst. of RAS, 2025