О сложности решения уравнений над графами Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 21, Number: 1, Pages: 62-69 Pages count : 8 DOI: 10.33048/semi.2024.21.005 | ||
| Tags | NP-completeness, generic complexity, graphs, equations. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
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.
Cite:
Рыбалов А.Н.
О сложности решения уравнений над графами
Сибирские электронные математические известия (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 РИНЦ
Dates:
| Submitted: | Nov 29, 2023 |
| Accepted: | Jan 10, 2024 |
| Published print: | Feb 13, 2024 |
| Published online: | Feb 13, 2024 |
Identifiers:
| Web of science: | WOS:001164416300005 |
| Scopus: | 2-s2.0-85191358037 |
| Elibrary: | 82336231 |
Citing:
Пока нет цитирований