No Access

The complexity of the equation solvability problem over semipattern groups

Attila Földvári

Institute of Mathematics, University of Debrecen, Pf. 400, Debrecen, 4002, Hungary

E-mail Address: foldvari.attila@science.unideb.hu

https://doi.org/10.1142/S0218196717500126Cited by:4 (Source: Crossref)

Abstract

The complexity of the equation solvability problem is known for nilpotent groups, for not solvable groups and for some semidirect products of Abelian groups. We provide a new polynomial time algorithm for deciding the equation solvability problem over certain semidirect products, where the first factor is not necessarily Abelian. Our main idea is to represent such groups as matrix groups, and reduce the original problem to equation solvability over the underlying field. Further, we apply this new method to give a much more efficient algorithm for equation solvability over nilpotent rings than previously existed.

Communicated by M. Volkov

Keywords:

AMSC: 20F10, 20G40, 16N40, 68Q17

References

1. S. Burris and J. Lawerence, The equivalence problem for finite rings, J. Symbolic Comput. 15 (1993) 67–71. Crossref, Web of Science, Google Scholar
2. S. Burris and J. Lawrence, Results on the equivalence problem for finite groups, Algebra Universalis 52(4) (2005) 495–500. Crossref, Web of Science, Google Scholar
3. P. Diaconis and I. M. Isaacs, Counting characters of upper triangular groups, Trans. Amer. Math. Soc. 360 (2008) 2359–2392. Crossref, Web of Science, Google Scholar
4. M. Goldmann and A. Russell, The complexity of solving equations over finite groups, in Proc. 14th Annual IEEE Conf. on Computational Complexity. Atlanta, Georgia, (1999), pp. 80–86. Google Scholar
5. M. Goldmann and A. Russell, The complexity of solving equations over finite groups, Inform. Comput. 178 (2002) 253–262. Crossref, Web of Science, Google Scholar
6. G. Horváth, The complexity of the equivalence end equation solvability problems over nilpotent rings and groups, Algebra Universalis 66(4) (2011) 391–403. Crossref, Web of Science, Google Scholar
7. G. Horváth, The complexity of the equivalence problem over finite rings, Glasgow Math. J. 54(1) (2012) 193–199. Crossref, Web of Science, Google Scholar
8. G. Horváth, The complexity of the equivalence end equation solvability problems over meta-abelian groups, J. Algebra 433 (2015) 208–230. Crossref, Web of Science, Google Scholar
9. G. Horváth, J. Lawrence, L. Mérai and Cs. Szabó, The complexity of the equivalence problem for non-solvable groups, Bull. London Math. Soc. 39(3) (2007) 433–438. Crossref, Web of Science, Google Scholar
10. G. Horváth, J. Lawerence and R. Willard, The equation solvability problem over finite rings (2016). Google Scholar
11. G. Horváth and Cs. Szabó, The complexity of checking identities over finite groups, Int. J. Algebra Comput. 16(5) (2006) 931–940. Link, Web of Science, Google Scholar
12. H. Hunt and R. Stearns, The complexity for equivalence for commutative rings, J. Symbolic Comput. 10 (1990) 411–436. Crossref, Web of Science, Google Scholar
13. I. M. Isaacs, Counting characters of upper triangular groups, J. Algebra 315(2) (2007) 698–719. Crossref, Web of Science, Google Scholar
14. G. Károlyi and Cs. Szabó, The complexity of the equation solvablity problem over nilpotent rings (2016). Google Scholar
15. J. Lawrence and R. Willard, The complexity of solving polynomial equations over finite rings (1997). Google Scholar
16. Cs. Szabó and V. Vértesi, The equivalence problem over finite rings, Internat. J. Algebra Comput. 21(3) (2011) 449–457. Link, Web of Science, Google Scholar
17. R. S. Wilson, On the structure of finite rings, Compositio Math. 26(1) (1973) 79–93. Web of Science, Google Scholar