109 urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891 JUCS - Journal of Universal Computer Science jucs 0948-695X 0948-6968 Journal of Universal Computer Science 10.3217/jucs-019-10-1375 23553 Research Article F.1.3 - Complexity Measures and Classes F.2.2 - Nonnumerical Algorithms and Problems Term Satisfiability Problem for Two-Element Algebras is in QL or is NQL-Complete Gorazd Tomasz A. gorazd@tcs.uj.edu.pl 1 Krzaczkowski Jacek 2 Jagiellonian University, Kraków, Poland Jagiellonian University Kraków Poland Maria Curie-Sklodowska University, Lublin, Poland Maria Curie-Sklodowska University Lublin Poland

Corresponding author: Tomasz A. Gorazd (gorazd@tcs.uj.edu.pl).

Academic editor:

2013 28 05 2013 19 10 1375 1395 CA0FA1C7-8165-533F-8EEB-CA1240E05CC6 5505611 17 08 2012 27 05 2013 Tomasz A. Gorazd, Jacek Krzaczkowski This article is freely available under the J.UCS Open Content License.

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.