On the Complexity of the Problem of Solving Systems of Tropical Polynomial Equations of Degree Two Научная публикация
| Конференция |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 июн. - 6 июл. 2024 , Омск |
||
|---|---|---|---|
| Сборник | Mathematical Optimization Theory and Operations Research: Recent Trends Сборник, Springer. 2024. 388 c. ISBN 978-3-031-73364-2. |
||
| Журнал |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
| Вых. Данные | Год: 2024, Том: 2239, Страницы: 73–84 Страниц : 11 DOI: 10.1007/978-3-031-73365-9_5 | ||
| Ключевые слова | Tropical algebra · NP-completeness · Generic-case complexity · Asymptotic density | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
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.
Библиографическая ссылка:
Buchinskiy I.M.
, Kotov M.V.
, Treier A.V.
On the Complexity of the Problem of Solving Systems of Tropical Polynomial Equations of Degree Two
В сборнике Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2024. – Т.2239. – C.73–84. – ISBN 978-3-031-73364-2. DOI: 10.1007/978-3-031-73365-9_5 Scopus OpenAlex
On the Complexity of the Problem of Solving Systems of Tropical Polynomial Equations of Degree Two
В сборнике Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2024. – Т.2239. – C.73–84. – ISBN 978-3-031-73364-2. DOI: 10.1007/978-3-031-73365-9_5 Scopus OpenAlex
Даты:
| Опубликована в печати: | 20 дек. 2024 г. |
| Опубликована online: | 20 дек. 2024 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85214256273 |
| OpenAlex: | W4405597819 |