The Complexity of Problems Connected with Two-element Algebras
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTEThe Complexity of Problems Connected with Two-element Algebras
Publication date: 15.12.2011
Reports on Mathematical Logic, 2011, Number 46, pp. 91-108
https://doi.org/10.4467/20842589RM.11.006.0284Authors
The Complexity of Problems Connected with Two-element Algebras
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.
[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.
Information: Reports on Mathematical Logic, 2011, Number 46, pp. 91-108
Article type: Original article
Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University
Maria Curie Skłodowska University, Lublin
Poland
Published at: 15.12.2011
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 1733
Number of downloads: 1089