О сложности решения уравнений в бициклическом моноиде Full article
| Journal |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 29, Number: 1, Pages: 8-17 Pages count : 10 DOI: 10.24147/1812-3996.2024.1.8-17 | ||
| Tags | уравнения, бициклический моноид, NP-трудность | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
В статье доказывается, что проблема разрешимости систем уравнений над бициклическим моноидом является NP-трудной. С другой стороны, доказывается полиномиальная разрешимость этой проблемы для некоторого естественного класса уравнений от одной переменной.
Cite:
Пичуев К.Д.
, Рыбалов А.Н.
О сложности решения уравнений в бициклическом моноиде
Вестник Омского университета. 2024. Т.29. №1. С.8-17. DOI: 10.24147/1812-3996.2024.1.8-17 РИНЦ OpenAlex
О сложности решения уравнений в бициклическом моноиде
Вестник Омского университета. 2024. Т.29. №1. С.8-17. DOI: 10.24147/1812-3996.2024.1.8-17 РИНЦ OpenAlex
Dates:
| Submitted: | Oct 24, 2023 |
| Published print: | Apr 25, 2024 |
| Published online: | Apr 25, 2024 |
Identifiers:
| Elibrary: | 65635096 |
| OpenAlex: | W4401342969 |
Citing:
Пока нет цитирований