JUCS - Journal of Universal Computer Science 19(10): 1375-1395, doi: 10.3217/jucs-019-10-1375
Term Satisfiability Problem for Two-Element Algebras is in QL or is NQL-Complete
Tomasz A. Gorazd‡, Jacek Krzaczkowski§‡ Jagiellonian University, Kraków, Poland§ Maria Curie-Sklodowska University, Lublin, Poland
Corresponding author: Tomasz Gorazd ( gorazd@tcs.uj.edu.pl ) © Tomasz Gorazd, Jacek Krzaczkowski. This article is freely available under the J.UCS Open Content License. Citation:
Gorazd TA, Krzaczkowski J (2013) Term Satisfiability Problem for Two-Element Algebras is in QL or is NQL-Complete. JUCS - Journal of Universal Computer Science 19(10): 1375-1395. https://doi.org/10.3217/jucs-019-10-1375 |  |
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
computational complexity, solving equations, algebra, clones, SAT