The Complexity of Problems Connected with Two-element Algebras

Tomasz A. Gorazd,

Jacek Krzaczkowski


This paper presents a complete classification of the complexity of the SAT and equivalence problems for two-element algebras. Cases of terms and polynomials are considered. We show that for any fixed two-element algebra the considered SAT problems are either in P or NP-complete and the equivalence problems are either in P or coNP-complete. We show that the complexity of the considered problems, parametrized by an algebra, are determined by the clone of term operations of the algebra and does not depend on generating functions for the clone.

Słowa kluczowe: sat, two-element algebras
[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
[2] D. M. Barrington, P. McKenzie, C. Moore, P. Tesson, D. Th´erien, Equation satisfiability and program satisfiability for finite monoids, Math. Found. Comp. Sci., (2000), 127-181.
[3] A.Bulatov, A dichotomy theorem for constraints on a three-element set, Proceedings of the 43rd Symposium on Foundations of Computer Science (2002), 649-658.
[4] S. Burris and J. Lawrence, The equivalence problem for finite rings, Journal of Symbolic Computation, 15 (1993), 67-71.
[5] S. Burris, J. Lawrence, Results on the equivalence problem for finite groups, Algebra Universalis, 52(4) (2004), 495-500.
[6] S. Burris, H.P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, 1981.
[7] M. Goldmann, A. Russel, The Complexity of Solving Equations over Finite Groups Inf. Comput., 178(1) (2002), 253-262.
[8] G.Horv´ath, J. Lawrence, L M´erai and C.Szab´o, The complexity of the equivalence problem for nonsolvable groups, Bull. London Math. Soc. 39 (2007), 433-438.
[9] G.Horv´ath, C.Szab´o, The complexity of checking identities over finite groups, Internat. J. Algebra Comput., 16(5) (2006), 931-939.
[10] H. Hunt, R. Stearns, The complexity for equivalence for commutative rings, Journal of Symbolic Computation, 10 (1990), 411-436.
[11] P.M.Idziak private comunication.
[12] O. Kl´ıma, Complexity issues of checking identities in finite monoids, Semigroup Forum, 79(3) (2009), 435-444.
[13] B. Larose, L. Za´dori, Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras, Internat. J. Algebra Comput., 16(3) (2006), 563-581.
[14] R.McKenzie, G.McNulty, W.Taylor, Algebras, Lattices, and Varieties. Vol. I. Mathematics Series, Wadsworth and Brooks/Cole, 1987.
[15] E.Post, The Two-valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies, N.5, Princeton University Press, 1941.
[16] T.J.Schaefer, The complexity of satisability problems, Proceedings of the 13th ACM Symposium on Theory of Computing, (1978), 216-226.
[17] B. Schwarz, The Complexity of Satisfiability Problems over Finite Lattices Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, LNCS 2996 (2004), 31-43.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.