Geodesic
Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 7-19.

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

Results are presented concerning the main problem of algebraic geometry over partially ordered sets from a computational point of view, namely, the solvability problem for systems of equations over a partial order. This problem is solvable in polynomial time if the directed graph corresponding to the partial order is a adjusted interval digraph, and is NP-complete if the base of the directed graph corresponding to the partial order is a cycle of length at least 4. We also present a result characterizing the possibility of transition from infinite systems of equations over partial orders to finite systems. Algebraic systems with this property are called equationally Noetherian. A partially ordered set is equationally Noetherian if and only if any of its upper and lower cones with base are finitely defined.
Keywords: systems of equations, computational complexity, partially ordered set, poset, equationally Noetherian property, cones, solvability. 
@article{PDM_2024_2_a1,
     author = {A. Yu. Nikitin and N. D. Kudyk},
     title = {Criterion for equational {Noetherianity} and complexity of the solvability problem for systems of equations over partially ordered sets},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {7--19},
     publisher = {mathdoc},
     number = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/}
}
TY  - JOUR
AU  - A. Yu. Nikitin
AU  - N. D. Kudyk
TI  - Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 7
EP  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/
LA  - ru
ID  - PDM_2024_2_a1
ER  - 
%0 Journal Article
%A A. Yu. Nikitin
%A N. D. Kudyk
%T Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 7-19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/
%G ru
%F PDM_2024_2_a1
A. Yu. Nikitin; N. D. Kudyk. Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets. Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 7-19. http://geodesic.mathdoc.fr/item/PDM_2024_2_a1/

[1] Daniyarova E. Yu., Myasnikov A. G., and Remeslennikov V. N., Algebraic Geometry over Algebraic Systems, SB RAS Publ., Novosibirsk, 2016, 243 pp. (in Russian)

[2] Gurov S. I., Boolean Algebras, Ordered Sets, Lattices: Definitions, Properties, Examples, Librocom Publ., M., 2013, 221 pp. (in Russian)

[3] Grätzer G., General Lattice Theory, Birkhäuser Verlag, Basel, 1978 | MR | Zbl

[4] Ore O., Theory of Graphs, AMS, 1965, 270 pp. | MR

[5] Feder T., Hell P., Hunag J., and Rafiey A., “Interval graphs, adjusted interval digraphs, and reflexive list homomorphism”, Discr. Appl. Math., 160:6 (2012), 697–707 | DOI | MR | Zbl

[6] Feder T., Hell P., and Hunag J., List Homomorphisms and Retractions to Reflexive Digraphs, 2007, 26 pp. http://theory.stanford.edu/t̃omas/ref.pdf

[7] Hell P. and Rafiey A., The Dichotomy of List Homomorphisms for Digraphs, 2010, arXiv: 1004.2908 | MR

[8] Feder T. and Hell P., “List homomorphisms to reflexive graphs”, J. Combinatorial Theory, 72:2 (1998), 236–250 | DOI | MR | Zbl