On complexity of the problem of solving systems of tropical polynomial equations of degree two Conference Abstracts
| Conference |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024 , Омск |
||
|---|---|---|---|
| Source | MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций», (Омск, 30 июня – 06 июля 2024 г.) Compilation, Издательство ОмГУ. Омск.2024. 109 c. ISBN 978-5-7779-2691-3. |
||
| Output data | Year: 2024, Pages: 54 Pages count : 1 | ||
| Tags | tropical algebra, generic-case complexity, asymptotic density, NP-completeness | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
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.
Cite:
Buchinskiy I.
, Kotov M.V.
, Treier A.V.
On complexity of the problem of solving systems of tropical polynomial equations of degree two
In compilation MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций», (Омск, 30 июня – 06 июля 2024 г.). – Издательство ОмГУ., 2024. – C.54. – ISBN 978-5-7779-2691-3.
On complexity of the problem of solving systems of tropical polynomial equations of degree two
In compilation MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций», (Омск, 30 июня – 06 июля 2024 г.). – Издательство ОмГУ., 2024. – C.54. – ISBN 978-5-7779-2691-3.
Dates:
| Submitted: | Apr 18, 2024 |
| Published print: | Jul 8, 2024 |
| Published online: | Jul 8, 2024 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований