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

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

Ivan Buchinskiy, Matvei Kotov, Alexander Treier

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. …

complexity computational eprint report problem report system systems