Generic polynomial algorithms for the knapsack problem in some matrix semigroups

Authors

  • Александр Рыбалов Институт математики им. С.Л.Соболева СО РАН

Keywords:

generic complexity, knapsack problem, integer matrices

Abstract

In this paper, we propose generic polynomial algorithms for
the knapsack problem over semigroups of non-negative integer matrices of arbitrary order and
semigroup of non-negative second-order integer matrices with determinant 1.

Published

2024-01-28

Issue

Vol. 20 No. 1 (2023): Том 20, №1, 2023

Section

Mathematical logic, algebra and number theory