Geodesic
On complexity of solving of equations over graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 62-69

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: NP-completeness, generic complexity, graphs
Mots-clés : equations. 
@article{SEMR_2024_21_1_a2,
     author = {A. N. Rybalov},
     title = {On complexity of solving of equations over graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {62--69},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On complexity of solving of equations over graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 62
EP  - 69
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/
LA  - ru
ID  - SEMR_2024_21_1_a2
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On complexity of solving of equations over graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 62-69
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/
%G ru
%F SEMR_2024_21_1_a2
A. N. Rybalov. On complexity of solving of equations over graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 62-69. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a2/