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
expand article infoTomasz A. Gorazd, Jacek Krzaczkowski§
‡ Jagiellonian University, Kraków, Poland§ Maria Curie-Sklodowska University, Lublin, Poland
Open Access
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.
computational complexity, solving equations, algebra, clones, SAT