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/

[1] Matiyasevich Yu. V., “Diophantineity of enumerable sets”, Doklady Akademii Nauk USSR, 191:2 (1970), 279–282 (in Russian)

[2] Mayr E. W., Meyer A. R., “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46:3 (1982), 305–329 | DOI | MR

[3] Cook S. A., “The complexity of theorem proving procedures”, Proc. 3d Ann. ACM Symp. Theory of Computing, N.Y., USA, 1971, 151–158

[4] Daniyarova E. Yu., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Structures, SB RAS, Novosibirsk, 2016, 288 pp. (in Russian)

[5] Garey M., Johnson D., Computers and Intractability, Freeman Co, N.Y., 1979, 340 pp. | MR | MR

[6] Werth T., Wörlein M., Dreweke A., et al., “DAG mining for code compaction”, Data Mining for Business Applications, eds. L. Cao, P. S. Yu, C. Zhang, H. Zhang, Springer, Boston, MA, 2009, 209–223

[7] Ore O., Theory of Graphs, Amer. Math. Soc., 1962, 270 pp. | MR | MR