The Complexity of Problems Connected with Two-element Algebras

Tomasz A. Gorazd; Jacek Krzaczkowski

Titles

Abstract

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.

Keywords

sat, two-element algebras

References

[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 satisﬁability and program satisﬁability for ﬁnite 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 ﬁnite rings, Journal of Symbolic Computation, 15 (1993), 67-71.

[5] S. Burris, J. Lawrence, Results on the equivalence problem for ﬁnite 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 ﬁnite 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 ﬁnite 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 ﬁnite 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 Satisﬁability Problems over Finite Lattices Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, LNCS 2996 (2004), 31-43.

Information

Information: Reports on Mathematical Logic, 2011, Number 46, pp. 91 - 108

DOI: https://doi.org/10.4467/20842589RM.11.006.0284

Article type: Original article

Titles:

Polish:

The Complexity of Problems Connected with Two-element Algebras

English:

The Complexity of Problems Connected with Two-element Algebras

Authors

Tomasz A. Gorazd

Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University

Jacek Krzaczkowski

Maria Curie Skłodowska University, Plac Marii Skłodowskiej-Curie 5, Lublin, Poland

Published at: 15.12.2011

Article status: Open

Licence: None

Percentage share of authors:

Tomasz A. Gorazd (Author) - 50%

Jacek Krzaczkowski (Author) - 50%

Article corrections:

-

Publication languages:

English

View count: 1701

Number of downloads: 1069

<p> The Complexity of Problems Connected with Two-element Algebras</p>

Pobierz pełny tekst

Titles

Abstract

Keywords

References

Information

Authors