On complexity of the satisfiability problem of systems over finite posets

DOI10.17223/20710410/39/8MaRDI QIDQ5151206zbMATH OpenOpenAlexWikidataFDO

Authors A. Yu. Nikitin, Alexander Rybalov

Publication date 17 February 2021

Published in Prikladnaya diskretnaya matematika (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/pdm614

zbMATH Keywords

NP-completenesspartially ordered setssystems of equations

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

Recommendations

• scientific article; zbMATH DE number 4114007
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• On solvability of systems of polynomial equations
• Term equation satisfiability over finite algebras
• Solving equations over small unary algebras

Cites work

• Algebraic geometry over algebraic structures. II: Foundations
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The complexity of theorem-proving procedures

Cited in

(10)

• Symmetric matrices whose entries are linear functions
• Itemset frequency satisfiability: complexity and axiomatization
• Systems of Diophantine equations over finite configurations
• Computational complexity of solving equation systems
• Solving equations over small unary algebras
• System Completion Problem: Theory and Applications
• scientific article; zbMATH DE number 4114007 (Why is no real title available?)
• Decidability of the restricted theories of a class of partial orders
• The NP-completeness of the consistency problem for systems of Diophantine equations over finite configurations
• Axiomatizability and decidability of universal theories of hereditary classes of models of finite and infinite languages

This page was built for publication: On complexity of the satisfiability problem of systems over finite posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151206)