pith. sign in

arxiv: 2503.09983 · v2 · submitted 2025-03-13 · 🧮 math.CO

On tropical knapsack-type problems

I. M. Buchinskiy , M. V. Kotov , A. V. Treier This is my paper

Pith reviewed 2026-05-23 00:56 UTC · model grok-4.3

classification 🧮 math.CO
keywords knapsack problemsubset sumNP-completenessmax-plus algebramax-times algebramatrix semigroupstropical semirings
0
0 comments X

The pith

Knapsack and subset sum are NP-complete for matrix semigroups in max-plus and max-times algebras.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the knapsack and subset sum problems after replacing ordinary addition and multiplication with the operations of max-plus and max-times algebras acting on matrices. It proves that both problems become NP-complete when the input consists of k by k matrices with non-negative entries under max-plus or positive entries under max-times. The authors also exhibit pseudo-polynomial algorithms that solve the problems and, for the max-times case, polynomial-time algorithms that work on generic instances. A reader would care because these results show how classic combinatorial hardness survives the move to algebraic structures commonly used in optimization and discrete-event systems.

Core claim

The knapsack problem and the subset sum problem are NP-complete for the semigroup of square matrices of size k by k with non-negative entries over the max-plus algebra and for the semigroup of square matrices of size k by k with positive entries over the max-times algebra. Pseudo-polynomial algorithms exist for both structures, and polynomial generic algorithms exist for the max-times semigroup.

What carries the argument

Polynomial-time reductions from the classical knapsack and subset sum decision problems to their versions inside the matrix semigroups over max-plus and max-times algebras.

If this is right

  • Both problems are NP-complete, so they admit no polynomial-time algorithms unless P equals NP.
  • Pseudo-polynomial algorithms solve the problems in time polynomial in the input size and the numeric values involved.
  • For the max-times semigroup, generic instances admit polynomial-time solutions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hardness results indicate that tropical matrix problems can inherit NP-completeness directly from their classical number-based counterparts.
  • The distinction between max-plus and max-times may allow similar generic polynomial algorithms to be found for other tropical semirings.
  • The existence of pseudo-polynomial but not strongly polynomial algorithms suggests the problems are weakly NP-complete in these settings.

Load-bearing premise

The standard knapsack and subset sum problems can be embedded into the matrix semigroups so that the yes/no answer is preserved by a polynomial-time reduction.

What would settle it

A polynomial-time algorithm deciding the subset-sum problem for k by k matrices over either algebra would falsify the NP-completeness claim.

read the original abstract

In this paper, we investigate the computational complexity of the knapsack problem and subset sum problem for the following tropical algebraic structures. We consider the semigroup of square matrices of size $k \times k$ with non-negative entries over the max-plus algebra and the semigroup square matrices of size $k \times k$ with positive entries over the max-times algebra. We prove that the knapsack problem and subset sum problem for these structures are $\textsf{NP}$-complete. We demonstrate that there are pseudo-polynomial algorithms to solve these problems. Also, we show that for the latter semigroup, there are polynomial generic algorithms to solve the knapsack problem and the subset sum problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper investigates the knapsack and subset sum problems over the semigroup of k×k matrices with non-negative entries under max-plus algebra and the semigroup of k×k matrices with positive entries under max-times algebra. It claims to prove that both problems are NP-complete via polynomial-time reductions from the classical versions, shows membership in NP using short certificates verifiable with polynomially many tropical matrix multiplications, provides pseudo-polynomial dynamic programming algorithms, and establishes polynomial-time generic algorithms for the max-times case on a Zariski-open set of instances.

Significance. If the explicit constructions and reductions hold, the work extends classical NP-completeness results to tropical matrix semigroups in a concrete way, supplying both hardness proofs and algorithmic upper bounds (including the generic polynomial-time procedures). The explicit embeddings and the separation between worst-case pseudo-polynomial time and generic polynomial time are useful contributions to the computational complexity of tropical algebra.

minor comments (2)
  1. [Abstract] Abstract: the sentence 'the semigroup square matrices of size k × k with positive entries over the max-times algebra' is missing the word 'of' after 'semigroup'.
  2. The manuscript refers to 'Zariski-open set of instances' for the generic algorithms but does not appear to define the open set explicitly or indicate how it is constructed from the input parameters.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript proves NP-completeness of knapsack and subset-sum decision problems over max-plus and max-times matrix semigroups by exhibiting explicit polynomial-time reductions from the classical versions of these problems. Membership in NP is shown via short certificates verified by polynomially many matrix multiplications. Separate pseudo-polynomial dynamic programs and Zariski-generic polynomial algorithms are derived directly from the algebraic definitions without reference to the hardness results. No equation or claim reduces to a fitted parameter, self-definition, or load-bearing self-citation; all steps are externally grounded in standard complexity reductions and direct algorithmic constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from computational complexity theory and tropical algebra; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of NP-completeness via polynomial reductions apply to the lifted problems.
    Invoked to establish the hardness results.

pith-pipeline@v0.9.0 · 5641 in / 923 out tokens · 51769 ms · 2026-05-23T00:56:10.444727+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    Dietzel, S

    S. Alhussaini, C. Collett, and S. Sergeev. “On the tropical two-sided discrete logarithm and a key exchange protocol based on the tropical algebra of pairs”. In: Communications in Algebra 52.10 (2024), pp. 4115–4134. doi: 10.1080/00927872.2024.2341814

    work page doi:10.1080/00927872.2024.2341814 2024

  2. [2]

    A Characterization of Wreath Products Where Knapsack Is Decidable

    P. Bergstr¨ aßer, M. Ganardi, and G. Zetzsche. “A Characterization of Wreath Products Where Knapsack Is Decidable”. In: 38th International Symposium on Theoretical Aspects of Com- puter Science (STACS 2021). Vol. 187. 2021, 11:1–11:17.doi: 10.4230/LIPIcs.STACS.2021. 11

    work page doi:10.4230/lipics.stacs.2021 2021

  3. [3]

    An attack on a key exchange protocol based on max-times and min-times algebras

    I. Buchinskiy, M. Kotov, and A. Treier. “An attack on a key exchange protocol based on max-times and min-times algebras”. In: Indian Journal of Pure and Applied Mathematics 56 (2025), pp. 180–190. doi: 10.1007/s13226-023-00469-0

    work page doi:10.1007/s13226-023-00469-0 2025

  4. [4]

    Analysis of four protocols based on tropical circu- lant matrices

    I. Buchinskiy, M. Kotov, and A. Treier. “Analysis of four protocols based on tropical circu- lant matrices”. In: Indian Journal of Pure and Applied Mathematics (2024). doi: 10.1007/ s13226-024-00737-7

    work page 2024

  5. [5]

    On the Complexity of the Problem of Solving Systems of Tropical Polynomial Equations of Degree Two

    I. Buchinskiy, M. Kotov, and A. Treier. “On the Complexity of the Problem of Solving Systems of Tropical Polynomial Equations of Degree Two”. In: Mathematical Optimization Theory and Operations Research: Recent Trends . Ed. by A. Eremeev et al. Communications in Computer and Information Science. Cham: Springer Nature Switzerland, 2024, pp. 73–84. doi: 10....

    work page doi:10.1007/978-3-031-73365-9_5 2024

  6. [6]

    Butkoviˇ c

    P. Butkoviˇ c. Max-linear systems: theory and algorithms . London: Springer, 2010. doi: 10. 1007/978-1-84996-299-5

    work page 2010

  7. [7]

    Knapsack problems—An overview of recent advances. Part I: Single knapsack problems

    V. Cacchiani et al. “Knapsack problems—An overview of recent advances. Part I: Single knapsack problems”. In: Computers & Operations Research 143 (2022), p. 105692. doi: 10. 1016/j.cor.2021.105692

    work page arXiv 2022

  8. [8]

    Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems

    V. Cacchiani et al. “Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems”. In: Computers & Operations Research 143 (2022), p. 105693. doi: 10.1016/j.cor.2021.105693

    work page doi:10.1016/j.cor.2021.105693 2022

  9. [9]

    T. H. Cormen et al. Introduction to algorithms . Cambridge, MA: MIT press, 2022

    work page 2022

  10. [10]

    Decidability of knapsack problem for Baumslag–Solitar group

    F. Dudkin and A. Treier. “Decidability of knapsack problem for Baumslag–Solitar group”. In: Journal of Physics: Conference Series . Vol. 1050. 1. IOP Publishing. 2018, p. 012022. doi: 10.1088/1742-6596/1050/1/012022

    work page doi:10.1088/1742-6596/1050/1/012022 2018

  11. [11]

    Knapsack problem for Baumslag–Solitair groups

    F. Dudkin and A. Treier. “Knapsack problem for Baumslag–Solitair groups”. In: Siberian Journal of Pure and Applied Mathematics 18.4 (2018). In Russian, pp. 43–55. doi: 10 . 33048/pam.2018.18.404

    work page 2018

  12. [12]

    An application of different dioids in public key cryptography

    M. I. Durcheva. “An application of different dioids in public key cryptography”. In: AIP Conference Proceedings. Vol. 1631. American Institute of Physics. 2014, pp. 336–343. doi: 10.1063/1.4902495. 15

    work page doi:10.1063/1.4902495 2014

  13. [13]

    Masset, R

    E. Frenkel, A. Nikolaev, and A. Ushakov. “Knapsack problems in products of groups”. In: Journal of Symbolic Computation 74 (2016), pp. 96–108. issn: 0747-7171. doi: 10.1016/j. jsc.2015.05.006

    work page doi:10.1016/j 2016

  14. [14]

    Knapsack and the power word problem in solv- able Baumslag–Solitar groups

    M. Ganardi, M. Lohrey, and G. Zetzsche. “Knapsack and the power word problem in solv- able Baumslag–Solitar groups”. In: International Journal of Algebra and Computation 33.03 (2023), pp. 617–639. doi: 10.1142/S0218196723500285

    work page doi:10.1142/s0218196723500285 2023

  15. [15]

    Knapsack Problems for Wreath Products

    M. Ganardi et al. “Knapsack Problems for Wreath Products”. In: 35th Symposium on The- oretical Aspects of Computer Science . Ed. by R. Niedermeier and B. Vall´ ee. Vol. 96. Leibniz International Proceedings in Informatics (LIPIcs). 2018, 32:1–32:13. isbn: 978-3-95977-062-0. doi: 10.4230/LIPIcs.STACS.2018.32

    work page doi:10.4230/lipics.stacs.2018.32 2018

  16. [16]

    M. R. Garey and D. S. Johnson. Computers and intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman, 1979

    work page 1979

  17. [17]

    Cyclic projectors and separation theorems in idempotent convex geometry

    S. Gaubert and S. Sergeev. “Cyclic projectors and separation theorems in idempotent convex geometry”. In: Journal of Mathematical Sciences 155 (2008), pp. 815–829. doi: 10.1007/ s10958-008-9243-8

    work page 2008

  18. [18]

    Tropical cryptography

    D. Grigoriev and V. Shpilrain. “Tropical cryptography”. In: Comm. Algebra 42.6 (2014), pp. 2624–2632. doi: 10.1080/00927872.2013.766827

    work page doi:10.1080/00927872.2013.766827 2014

  19. [19]

    Castelli, G

    D. Grigoriev and V. Shpilrain. “Tropical cryptography II: extensions by homomorphisms”. In: Comm. Algebra 47.10 (2019), pp. 4224–4229. doi: 10.1080/00927872.2019.1581213

    work page doi:10.1080/00927872.2019.1581213 2019

  20. [20]

    On the complexity of model checking counter automata

    C. Haase. “On the complexity of model checking counter automata”. Ph.D. thesis. University of Oxford, 2012

    work page 2012

  21. [21]

    A closer look at the tropical cryptography

    S. Isaac and D. Kahrobaei. “A closer look at the tropical cryptography”. In: Int. J. Comput. Math.: Comput. Syst. Theory 6.2 (2021), pp. 137–142. doi: 10 . 1080 / 23799927 . 2020 . 1862303

    work page 2021

  22. [22]

    Reducibility among combinatorial problems

    R. Karp. “Reducibility among combinatorial problems”. In: Complexity of Computer Com- putation (1972), pp. 85–104. doi: 10.1007/978-1-4684-2001-2_9

    work page doi:10.1007/978-1-4684-2001-2_9 1972

  23. [23]

    Knapsack and subset sum problems in nilpotent, poly- cyclic, and co-context-free groups

    D. K¨ onig, M. Lohrey, and G. Zetzsche. “Knapsack and subset sum problems in nilpotent, poly- cyclic, and co-context-free groups”. In: Algebra and Computer Science 677 (2016), pp. 138–

    work page 2016

  24. [24]

    doi: 10.1090/conm/677/13625

    work page doi:10.1090/conm/677/13625

  25. [25]

    Analysis of a key exchange protocol based on tropical matrix algebra

    M. Kotov and A. Ushakov. “Analysis of a key exchange protocol based on tropical matrix algebra”. In: J. Math. Cryptol. 12.3 (2018), pp. 137–141. doi: 10.1515/jmc-2016-0064

    work page doi:10.1515/jmc-2016-0064 2018

  26. [26]

    Knapsack in hyperbolic groups

    M. Lohrey. “Knapsack in hyperbolic groups”. In: Journal of Algebra 545 (2020), pp. 390–415. doi: 10.1016/j.jalgebra.2019.04.008

    work page doi:10.1016/j.jalgebra.2019.04.008 2020

  27. [27]

    Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products

    M. Lohrey and G. Zetzsche. “Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products”. In: 33rd Symposium on Theoretical Aspects of Computer Science . Vol. 47. 2016, 50:1–50:14. doi: 10.4230/LIPIcs.STACS.2016.50

    work page doi:10.4230/lipics.stacs.2016.50 2016

  28. [28]

    The Complexity of Knapsack in Graph Groups

    M. Lohrey and G. Zetzsche. “The Complexity of Knapsack in Graph Groups”. In: 34th Sympo- sium on Theoretical Aspects of Computer Science . Vol. 66. Leibniz International Proceedings in Informatics. 2017, 52:1–52:14. doi: 10.4230/LIPIcs.STACS.2017.52

    work page doi:10.4230/lipics.stacs.2017.52 2017

  29. [29]

    Knapsack problem for nilpotent groups

    A. Mishchenko and A. Treier. “Knapsack problem for nilpotent groups”. In: Groups Com- plexity Cryptology 9.1 (2017), pp. 87–98. doi: 10.1515/gcc-2017-0006

    work page doi:10.1515/gcc-2017-0006 2017

  30. [30]

    On NP-completeness of subset sum problem for Lamplighter group

    A. Mishchenko and A. Treier. “On NP-completeness of subset sum problem for Lamplighter group”. In: Journal of Physics: Conference Series . Vol. 1050. IOP Publishing. 2018, p. 012055. doi: 10.1088/1742-6596/1050/1/012055

    work page doi:10.1088/1742-6596/1050/1/012055 2018

  31. [31]

    Thermal effects and their compen- sation in advanced virgo.Journal of Physics: Confer- ence Series, 363:012016, jun 2012

    A. Mishchenko and A. Treier. “Universal input of knapsack problem for groups”. In:Journal of Physics: Conference Series. Vol. 1050. IOP Publishing. 2018, p. 012054. doi: 10.1088/1742- 6596/1050/1/012054

    work page doi:10.1088/1742- 2018

  32. [32]

    B. M. Moret. The Theory of Computation . USA: Addison-Wesley, 1997. doi: 10 . 5555 / 550016. 16

    work page 1997

  33. [33]

    Public key cryptography based on tropical algebra

    A. Muanalifah. “Public key cryptography based on tropical algebra”. PhD thesis. University of Birmingham, 2023

    work page 2023

  34. [34]

    On convergence of stringy motives of wild p^n -cyclic quotient singularities

    A. Muanalifah and S. Sergeev. “On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product”. In: Communications in Algebra 50.2 (2022), pp. 861–879. doi: 10.1080/00927872.2021.1975125

    work page doi:10.1080/00927872.2021.1975125 2022

  35. [35]

    Knapsack problems in groups

    A. Myasnikov, A. Nikolaev, and A. Ushakov. “Knapsack problems in groups”. In: Mathematics of Computation 84.292 (2015), pp. 987–1016. doi: 10.1090/S0025-5718-2014-02880-9

    work page doi:10.1090/s0025-5718-2014-02880-9 2015

  36. [36]

    Generic polynomial algorithms for the knapsack problem in some matrix semigroups,

    A. N. Rybalov. “Generic polynomial algorithms for the knapsack problem in some matrix semigroups,” in: Siberian Electronic Mathematical Reports 20.1 (2023). In Russian, pp. 100–

    work page 2023

  37. [37]

    doi: 10.33048/semi.2023.20.009

    work page doi:10.33048/semi.2023.20.009 2023

  38. [38]

    On generic complexity of the subset sum problem for monoids and groups of integer matrices of order 2

    A. N. Rybalov. “On generic complexity of the subset sum problem for monoids and groups of integer matrices of order 2”. In: Vestnik of Omsk University 25.4 (2020). In Russian, pp. 10–

    work page 2020

  39. [39]

    doi: 10.24147/1812-3996.2020.25(4).10-15

    work page doi:10.24147/1812-3996.2020.25(4).10-15 2020

  40. [40]

    On generic complexity of the subset sum problem for semigroups of integer matrices

    A. N. Rybalov. “On generic complexity of the subset sum problem for semigroups of integer matrices”. In: Prikladnaya Diskretnaya Matematika 4 (2020). In Russian, pp. 118–126. doi: 10.17223/20710410/50/9

    work page doi:10.17223/20710410/50/9 2020

  41. [41]

    A note on square roots of nonnegative matrices

    Y. Shitov. “A note on square roots of nonnegative matrices”. In: Linear Algebra and Its Applications 497 (2016), pp. 62–65. doi: 10.1016/j.laa.2016.02.022

    work page doi:10.1016/j.laa.2016.02.022 2016

  42. [42]

    On square roots of matrices over the max-time semiring R+

    I. M. Sulandra and A. N. Isnia. “On square roots of matrices over the max-time semiring R+”. In: Journal of Physics: Conference Series . Vol. 1872. IOP Publishing. 2021, p. 012014. doi: 10.1088/1742-6596/1872/1/012014

    work page doi:10.1088/1742-6596/1872/1/012014 2021

  43. [43]

    Constrained inhomogeneous spherical equations: average-case hardness

    A. Ushakov. “Constrained inhomogeneous spherical equations: average-case hardness”. In: journal of Groups, complexity, cryptology 16.1 (2024), 3:1–3:18. doi: 10.46298/jgcc.2024. 16.1.13555. I. M. Buchinskiy , Sobolev Institute of Mathematics of SB RAS, Omsk, Russia Email address : buchvan@mail.ru M. V. Kotov , Sobolev Institute of Mathematics of SB RAS, O...

    work page doi:10.46298/jgcc.2024 2024