|
This article is cited in 5 scientific papers (total in 5 papers)
Mathematical Backgrounds of Informatics and Programming
On complexity of the satisfiability problem of systems over finite posets
A. Y. Nikitin, A. N. Rybalov Omsk State Technical University, Omsk, Russia
Abstract:
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.
Citation:
A. Y. Nikitin, A. N. Rybalov, “On complexity of the satisfiability problem of systems over finite posets”, Prikl. Diskr. Mat., 2018, no. 39, 94–98
Linking options:
https://www.mathnet.ru/eng/pdm614 https://www.mathnet.ru/eng/pdm/y2018/i1/p94
|
Statistics & downloads: |
Abstract page: | 239 | Full-text PDF : | 69 | References: | 37 |
|