Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/1

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.