Geodesic
On complexity of the satisfiability problem of systems over finite posets
Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 94-98

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

Classical algebraic geometry studies sets of solutions of algebraic equations over the fields of real and complex numbers. In the frameworks of computational algebraic geometry, several algorithms were proposed (for example, the Buchberger algorithm) for solving systems of polynomial equations over these fields. Universal algebraic geometry studies systems of equations over arbitrary algebraic structures. The equations are atomic formulas in the language of an algebraic structure. In this article, we consider the problem of recognizing the solvability of systems of equations over finite partially ordered sets. We prove that this problem is NP-complete in the case when we seek a solution consisting of pairwise distinct elements of a finite partially ordered set.
Keywords: partially ordered sets, systems of equations, NP-completeness. 
@article{PDM_2018_1_a7,
     author = {A. Y. Nikitin and A. N. Rybalov},
     title = {On complexity of the satisfiability problem of systems over finite posets},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {94--98},
     publisher = {mathdoc},
     number = {1},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_1_a7/}
}
TY  - JOUR
AU  - A. Y. Nikitin
AU  - A. N. Rybalov
TI  - On complexity of the satisfiability problem of systems over finite posets
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 94
EP  - 98
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_1_a7/
LA  - ru
ID  - PDM_2018_1_a7
ER  - 
%0 Journal Article
%A A. Y. Nikitin
%A A. N. Rybalov
%T On complexity of the satisfiability problem of systems over finite posets
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 94-98
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_1_a7/
%G ru
%F PDM_2018_1_a7
A. Y. Nikitin; A. N. Rybalov. On complexity of the satisfiability problem of systems over finite posets. Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 94-98. http://geodesic.mathdoc.fr/item/PDM_2018_1_a7/