Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
91--108
Opis fizyczny
Bibliogr. 17 poz., rys.
Twórcy
autor
autor
- Theoretical Computer Science Department, Jagiellonian University, Krakow, Poland, tomasz.gorazd@uj.edu.pl
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUJ8-0008-0006