Generic complexity of~the~membership problem for~semigroups of integer matrices

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 95-101.

Résumé

The membership problem for finitely generated subgroups (subsemigroups) of groups (semigroups) is a classical algorithmic problem, actively studied for many decades. Already for sufficiently simple groups and semigroups, this problem becomes undecidable. For example, K. A. Mikhailova in 1966 proved the undecidability of the membership problem for finitely generated subgroups (hence and for subsemigroups) of a direct product $F_2 \times F_2$ of two free groups of rank $2$. Since, by the well-known Sanov theorem, the group $F_2$ has an exact representation by integer matrices of order $2$, the group $F_2 \times F_2$ is a subgroup of the group $\text{GL}_4 (\mathbb{Z})$ of integer matrices of order $4$. It easily implies the undecidability of this problem for the group $\text{GL}_{k} (\mathbb{Z})$ for $k \geq 4$. Undecidability of the membership problem for finitely generated subsemigroups of semigroups of integer matrices of order $\geq 3$ follows from Paterson's result proved in 1970. In this paper, we propose a strongly generic algorithm deciding the membership problem for semigroups of integer matrices of arbitrary order for inputs from a subset whose sequence of frequencies exponentially fast converges to $1$ with increasing size.

Détail

Keywords: generic complexity, membership problem, semigroups of integer matrices.

Bibliographie

[1] Mikhaylova K. A., “Membership problem for direct products of groups”, Matematicheskiy Sbornik, 112:2 (1966), 241–251 (in Russian) | Zbl

[2] Paterson M. S., “Unsolvability in $3\times 3$ matrices”, Studies Appl. Math., 49:1 (1970), 105–107 | DOI | MR | Zbl

[3] Halava V., Harju T., “Mortality in matrix semigroups”, Amer. Math. Monthly, 108:7 (2001), 649–653 | DOI | MR | Zbl

[4] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[5] Babai L., Erdos P, Selkow S., “Random graph isomorphism”, SIAM J. Computing, 9:3 (1980), 628–635 | DOI | MR | Zbl

[6] Gimadi E. X., Glebov N. I., Perepelitsa V. A., “Algorithms with bounds for problems of discrete optimization”, Problemy Kibernetiki, 31 (1975), 35–42 (in Russian)

[7] Seliverstov A.V., “Binary solutions to large systems of linear equations”, Prikladnaya Diskretnaya Matematika, 2021, no. 52, 5–15 (in Russian) | MR | Zbl

[8] Gurevich Y., “Average case completeness”, J. Computer System Sci., 42 (1991), 346–398 | DOI | MR | Zbl

[9] Levin L., “Average case complete problems”, SIAM J. Computing, 15 (1987), 285–286 | DOI | MR

[10] Rybalov A., “A generic algorithm for the membership problem in semigroups of integer matrices”, Vestnik Omskogo universiteta, 25:3 (2020), 8–12

[11] Hirschfeldt D., “Some questions in computable mathematics”, Computability and Complexity, 2017, 22–55 | DOI | MR | Zbl

[12] Meyer A., “An open problem on creative sets”, Recursive Function Theory Newsletter, 4 (1973), 15–16

[13] Jockusch C., Schupp P., “Generic computability, Turing degrees, and asymptotic density”, J. London Math. Soc., 85:2 (2012), 472–490 | DOI | MR | Zbl

[14] Schwartz J., “Fast probabilistic algorithms for verification of polynomial identities”, J. ACM, 27:4 (1980), 701–717 | DOI | MR | Zbl

[15] Zippel R., “Probabilistic algorithms for sparse polynomials”, Symbolic Algebraic Computation, 72 (1979), 216–226 | DOI | MR | Zbl

[16] DeMillo R., Lipton R., “A probabilistic remark on algebraic program testing”, Inform. Processing Lett., 7 (1978), 193–195 | DOI | Zbl