О сложности решения уравнений над графами Научная публикация
| Журнал |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 21, Номер: 1, Страницы: 62-69 Страниц : 8 DOI: 10.33048/semi.2024.21.005 | ||
| Ключевые слова | NP-completeness, generic complexity, graphs, equations. | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
In this paper the computational complexity of the problem of determining the compatibility of systems of equations without constants over an arbitrary fixed finite graph is studied. In this case, the graph is fixed, and the input is an arbitrary system of equations in the graph language without constants. A criterion is given for NP-completeness and polynomial decidability of this problem. Also its generic decidability in polynomial time is proved.
Библиографическая ссылка:
Рыбалов А.Н.
О сложности решения уравнений над графами
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. Т.21. №1. С.62-69. DOI: 10.33048/semi.2024.21.005 WOS Scopus РИНЦ
О сложности решения уравнений над графами
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. Т.21. №1. С.62-69. DOI: 10.33048/semi.2024.21.005 WOS Scopus РИНЦ
Даты:
| Поступила в редакцию: | 29 нояб. 2023 г. |
| Принята к публикации: | 10 янв. 2024 г. |
| Опубликована в печати: | 13 февр. 2024 г. |
| Опубликована online: | 13 февр. 2024 г. |
Идентификаторы БД:
| Web of science: | WOS:001164416300005 |
| Scopus: | 2-s2.0-85191358037 |
| РИНЦ: | 82336231 |
Цитирование в БД:
Пока нет цитирований