Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2018, Number 39, Pages 94–98
DOI: https://doi.org/10.17223/20710410/39/8
(Mi pdm614)
 

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
Full-text PDF (611 kB) Citations (5)
References:
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.
Funding agency Grant number
Russian Science Foundation 17-11-01117
Bibliographic databases:
Document Type: Article
UDC: 510.52
Language: Russian
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
Citation in format AMSBIB
\Bibitem{NikRyb18}
\by A.~Y.~Nikitin, A.~N.~Rybalov
\paper On complexity of the satisfiability problem of systems over finite posets
\jour Prikl. Diskr. Mat.
\yr 2018
\issue 39
\pages 94--98
\mathnet{http://mi.mathnet.ru/pdm614}
\crossref{https://doi.org/10.17223/20710410/39/8}
\elib{https://elibrary.ru/item.asp?id=32724378}
Linking options:
  • https://www.mathnet.ru/eng/pdm614
  • https://www.mathnet.ru/eng/pdm/y2018/i1/p94
  • This publication is cited in the following 5 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:239
    Full-text PDF :69
    References:37
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024