Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 19 / Issue 10

available in:   PDF (232 kB) PS (363 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-019-10-1375


Term Satisfiability Problem for Two-Element Algebras is in QL or is NQL-Complete

Tomasz A. Gorazd (Jagiellonian University, Poland)

Jacek Krzaczkowski (Maria Curie-Sklodowska University, Poland)

Abstract: We show that the term satisfiability problem for finite algebras is in NQL. Moreover we present a complete classification of the computational complexity of the term satisfiability problem for two-element algebras. We show that for any fixed twoelement algebra the problem is either in QL or NQL-complete.

We show that the complexity of the considered problem, parameterized by an algebra, is determined by the clone of term operations of the algebra.

Keywords: SAT, algebra, clones, computational complexity, solving equations

Categories: F.1.3, F.2.2