The complexity of the word-problem for finite matrix rings
HTML articles powered by AMS MathViewer
- by Csaba Szabó and Vera Vértesi PDF
- Proc. Amer. Math. Soc. 132 (2004), 3689-3695 Request permission
Abstract:
We analyze the so-called word-problem for $M_2(Z_2)$, the ring of $2\times 2$ matrices over $Z_2$. We prove that the term-equivalence problem for the semigroup (and so for the ring) $M_2(Z_2)$ is coNP-complete.References
- David Mix Barrington, Pierre McKenzie, Cris Moore, Pascal Tesson, and Denis Thérien, Equation satisfiability and program satisfiability for finite monoids, Mathematical foundations of computer science 2000 (Bratislava), Lecture Notes in Comput. Sci., vol. 1893, Springer, Berlin, 2000, pp. 172–181. MR 1844742, DOI 10.1007/3-540-44612-5_{1}3
- Stanley Burris and John Lawrence, The equivalence problem for finite rings, J. Symbolic Comput. 15 (1993), no. 1, 67–71. MR 1210448, DOI 10.1006/jsco.1993.1004
- H. B. Hunt III and R. E. Stearns, The complexity of equivalence for commutative rings, J. Symbolic Comput. 10 (1990), no. 5, 411–436. MR 1087713, DOI 10.1016/S0747-7171(08)80053-3
- A. Kisieliewicz, personal communication, 2002.
- J. Lawrence and R. Willard, The complexity of solving polynomial equations over finite rings, manuscript, 1997.
- V. Yu. Popov and M. V. Volkov, Complexity of checking identities and quasi-identities in finite semigroups, Journal of Symblic logic (to appear).
- S. Seif and Cs. Szabó, The computational complexity of checking identites in simple semigroups and matrix semigroups over finite fields, Semigroup Forum (to appear 2002).
Additional Information
- Csaba Szabó
- Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
- Email: csaba@cs.elte.hu
- Vera Vértesi
- Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, 1117 Budapest, Pázmány Péter sétány 1/c, Hungary
- Email: wera13@cs.elte.hu
- Received by editor(s): September 5, 2002
- Received by editor(s) in revised form: July 24, 2003
- Published electronically: July 20, 2004
- Communicated by: Lance W. Small
- © Copyright 2004 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 132 (2004), 3689-3695
- MSC (2000): Primary 68Q17, 03C13
- DOI: https://doi.org/10.1090/S0002-9939-04-07488-X
- MathSciNet review: 2084092