Generic polynomial algorithms for the knapsack problem in some matrix semigroups
From MaRDI portal
Publication:6587364
DOI10.33048/SEMI.2023.20.009MaRDI QIDQ6587364FDOQ6587364
Authors: Alexander Rybalov 
Publication date: 14 August 2024
Published in: Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)
Recommendations
- On generic complexity of the subset sum problem for semigroups of integer matrices
- Generic complexity of the membership problem for semigroups of integer matrices
- scientific article; zbMATH DE number 3876925
- Knapsack problems in groups
- An algorithm for solving a class of knapsack problems and its generalization
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Gaussian elimination is not optimal
- On multiplication of 2 \(\times\) 2 matrices
- Knapsack problems in groups
- Generic-case complexity, decision problems in group theory, and random walks.
- Generic computability, Turing degrees, and asymptotic density
- Some Questions in Computable Mathematics
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Matrix multiplication, a little faster
- Die Gruppe der dreidimensionalen Gittertransformationen.
- A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix
- Deterministic computation of the characteristic polynomial in the time of matrix multiplication
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Fast commutative matrix algorithms
- On generic complexity of the subset sum problem for semigroups of integer matrices
This page was built for publication: Generic polynomial algorithms for the knapsack problem in some matrix semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6587364)
