The complexity of problems connected with two-element algebras

• Autorzy: Gorazd T. , Krzaczkowski J.
• Języki publikacji: EN

Abstrakty

EN

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 equiva- lence 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 al- gebra and does not depend on generating functions for the clone.

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2011
• Tom: Vol. 46
• Strony: 91--108
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Gorazd T.

autor

Krzaczkowski J.

• Theoretical Computer Science Department, Jagiellonian University, Krakow, Poland,

Bibliografia

• [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.Horvath, J. Lawrence, L Merai and C.Szabó, The complexity of the equivalence problem for nonsolvable groups, Bull. London Math. Soc. 39 (2007), 433-438.
• [9] G.Horvath, C.Szabó, 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. Klima, Complexity issues of checking identities in finite monoids, Semigroup Forum, 79(3) (2009), 435-444.
• [13] B. Larose, L. Zadori, 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.