О сложности решения уравнений в бициклическом моноиде Научная публикация
| Журнал |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 29, Номер: 1, Страницы: 8-17 Страниц : 10 DOI: 10.24147/1812-3996.2024.1.8-17 | ||
| Ключевые слова | уравнения, бициклический моноид, NP-трудность | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
В статье доказывается, что проблема разрешимости систем уравнений над бициклическим моноидом является NP-трудной. С другой стороны, доказывается полиномиальная разрешимость этой проблемы для некоторого естественного класса уравнений от одной переменной.
Библиографическая ссылка:
Пичуев К.Д.
, Рыбалов А.Н.
О сложности решения уравнений в бициклическом моноиде
Вестник Омского университета. 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
Даты:
| Поступила в редакцию: | 24 окт. 2023 г. |
| Опубликована в печати: | 25 апр. 2024 г. |
| Опубликована online: | 25 апр. 2024 г. |
Идентификаторы БД:
| РИНЦ: | 65635096 |
| OpenAlex: | W4401342969 |
Цитирование в БД:
Пока нет цитирований