| О сложности решения уравнений в бициклическом моноиде | |
| Пичуев К. Д.1, Рыбалов А. Н.2 | |
| 1.1Институт математики им. С.Л.~Соболева СО РАН, Омск, Россия | |
| Дата поступления 2024.10.09 | Аннотация. {В данной статье доказывается, что проблема разрешимости систем уравнений над бициклическим моноидом является NP-трудной. С другой стороны, доказывается полиномиальная разрешимость этой проблемы для некоторого естественного класса уравнений от одной переменной. Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. |
| Ключевые слова {уравнения, бициклический моноид, NP-трудность | |
Библиография \bibitem{Mak} Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе // Математический сборник. 1977. Т.~103, №~2. С.~147--236. \bibitem{Rom} Романьков В.А. Об универсальной теории нильпотентных групп // Математические заметки. 1979. Т.~25, №~4. С.~487--495. \bibitem{And} Andersen O. Ein Berichtuber die Struktur abstrakter Halbgruppen. PhD Thesis. Hamburg, 1952. \bibitem{HKP} Harju T., Karhumaki J., Plandowski W. Compactness of systems of equations in semigroups // Automata, Languages and Programming: 22nd International Colloquium, (ICALP, 1995, Szeged: Hungary). LNCS, 1995. Vol.~944. P.~444--454. \bibitem{DL} Diekert V., Lohrey M. Word Equations over Graph Products // IJAC. 2008. Vol.~18. P.~493--533. | |
Сведения о финансировании и благодарности Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| On the complexity of solving of equations in the bicyclic monoid | |
| Pichuev K. D.1, Rybalov A. N.2 | |
| 1.1Sobolev Institute of Mathematics SB RAS, Omsk, Russia | |
| Received 2024.10.09 | Abstract. In this article we prove that the problem of solvability of systems of equations over the bicyclic a monoid is NP-hard. On the other hand, we prove polynomial decidability of this problem for some natural class of equations in one variable. The work of the second author was carried out in the framework of the State Contract of the Sobolev Institute of Mathematics, Project No. FWNF-2022-0003. |
| Keywords equations, bicyclic monoid, NP-hardness | |
References \bibitem{Mak} Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе // Математический сборник. 1977. Т.~103, №~2. С.~147--236. \bibitem{Rom} Романьков В.А. Об универсальной теории нильпотентных групп // Математические заметки. 1979. Т.~25, №~4. С.~487--495. \bibitem{And} Andersen O. Ein Berichtuber die Struktur abstrakter Halbgruppen. PhD Thesis. Hamburg, 1952. \bibitem{HKP} Harju T., Karhumaki J., Plandowski W. Compactness of systems of equations in semigroups // Automata, Languages and Programming: 22nd International Colloquium, (ICALP, 1995, Szeged: Hungary). LNCS, 1995. Vol.~944. P.~444--454. \bibitem{DL} Diekert V., Lohrey M. Word Equations over Graph Products // IJAC. 2008. Vol.~18. P.~493--533. | |
Acknowledgements Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| Сведения об авторах Пичуев К. Д. 1.1 Рыбалов А. Н. |
| About the authors Pichuev K. D. 1.1 Rybalov A. N. |
