On the complexity of the problem of solving systems of tropical polynomial equations of degree two

Ivan Buchinskiy; Matvei Kotov; Alexander Treier

Paper 2024/576

On the complexity of the problem of solving systems of tropical polynomial equations of degree two

Ivan Buchinskiy

, Sobolev Institute of Mathematics of SB RAS

Matvei Kotov

, Sobolev Institute of Mathematics of SB RAS

Alexander Treier

, Sobolev Institute of Mathematics of SB RAS

Abstract

In this paper, we investigate the computational complexity of the problem of solving a one-sided system of equations of degree two of a special form over the max-plus algebra. Also, we consider the asymptotic density of solvable systems of this form. Such systems have appeared during the analysis of some tropical cryptography protocols that were recently suggested. We show how this problem is related to the integer linear programming problem and prove that this problem is NP-complete. We show that the asymptotic density of solvable systems of this form with some restrictions on the coefficients, the number of variables, and the number of equations is 0. As a corollary, we prove that this problem (with some restrictions on the coefficients, the number of variables, and the number of equations) is decidable generically in polynomial time.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. Communications in Computer and Information Science
DOI: 10.1007/978-3-031-73365-9_5
Keywords: tropical cryptography key exchange protocol tropical algebra NP-completeness generic-case complexity asymptotic density
Contact author(s): buchvan @ mail ru
matvej kotov @ gmail com
alexander treyer @ gmail com
History: 2024-12-23: revised; 2024-04-15: received; See all versions
Short URL: https://ia.cr/2024/576
License: CC BY

BibTeX

@misc{cryptoeprint:2024/576,
      author = {Ivan Buchinskiy and Matvei Kotov and Alexander Treier},
      title = {On the complexity of the problem of solving systems of tropical polynomial equations of degree two},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/576},
      year = {2024},
      doi = {10.1007/978-3-031-73365-9_5},
      url = {https://eprint.iacr.org/2024/576}
}