×

Solving the conjugacy decision problem via machine learning. (English) Zbl 1481.20119

Summary: Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this paper, we seek to extend these techniques to finitely presented non-free groups, with a particular emphasis on polycyclic and metabelian groups that are of interest to non-commutative cryptography. As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and \(N\)-tuple neural network models are evaluated for several non-free groups. The very high accuracy of these classifiers suggests an underlying mathematical relationship with respect to conjugacy in the tested groups.

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68T05 Learning and adaptive systems in artificial intelligence
20-08 Computational methods for problems pertaining to group theory

Software:

Scikit; GAP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bledsoe, [Bledsoe and Browning 59] W. W.; Browning, I., Papers Presented at the Eastern Joint IRE-AIEE-ACM Computer Conference, Pattern Recognition and Reading by Machine., 225-232 (1959), ACM
[2] Breiman, [Breiman 01] L., Random Forests., Mach. Learn., 45, 1, 5-32 (2001) · Zbl 1007.68152
[3] Dehn, [Dehn 11] M., Über Unendliche Diskontinuierliche Gruppen., Math. Annal., 71, 1, 116-144 (1911) · JFM 42.0508.03
[4] Eick, [Eick et al. 13] B.; Nickel, W.; Horn, M., Polycyclic, Computation with Polycyclic Groups, Version 2.11. (2013)
[5] Epstein, [Epstein and Holt 06] D.; Holt, D., The Linearity of the Conjugacy Problem in Word-Hyperbolic Groups., Int. J. Algebra Comput., 16, 2, 287-305 (2006) · Zbl 1141.20028
[6] Groups, [GAP 16] GAP -, Algorithms, and Programming, Version 4.8.5. (2016)
[7] Garber, [Garber et al. 15] D.; Kahrobaei, D.; Lam, H. T., Length-Based Attack for Polycyclic Groups., J. Math. Cryptol. De Gruyter, 9, 1, 33-44 (2015)
[8] Gryak, [Gryak and Kahrobaei 16] J.; Kahrobaei, D., The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems., Groups Complex. Cryptol., 8, 2, 171-186 (2016) · Zbl 1353.94050
[9] Gryak, [Gryak et al. 16] J.; Kahrobaei, D.; Martinez-Perez, C., On the Conjugacy Problem in Certain Metabelian Groups., arXiv preprint arXiv:1610.06503 (2016)
[10] Haralick, [Haralick 15] R., N-Tuple Method (2015), University Lecture
[11] Haralick, [Haralick et al. 04] R.; Miasnikov, A. D.; Myasnikov, A. G., Pattern Recognition Approaches to Solving Combinatorial Problems in Free Groups. (2004) · Zbl 1066.20041
[12] Holt, [Holt et al. 05] D. F.; Eick, B.; O’Brien, E. A., Handbook of Computational Group Theory. Discrete Mathematics and its Applications (Boca Raton) (2005), Boca Raton, FL: Chapman & Hall/CRC, Boca Raton, FL · Zbl 1091.20001
[13] Kapovich, [Kapovich et al. 03] I.; Myasnikov, A. G.; Schupp, P.; Shpilrain, V., Generic-Case Complexity, Decision Problems in Group Theory, and Random Walks., J. Algebra, 264, 2, 665-694 (2003) · Zbl 1041.20021
[14] Knuth, [Knuth and Bendix 70] D. E.; Bendix, P. B., Simple Word Problems in Universal Algebras., Comput. Problem. Abstract Algebra, 263-297 (1970) · Zbl 0188.04902 · doi:10.1016/B978-0-08-012975-4.50028-X
[15] Kołcz, [Kołcz and Allinson 94] A.; Allinson, N. M., Application of the CMAC Input Encoding Scheme in the N-Tuple Approximation Network., IEE Proc.-Comput. Digital Techn., 141, 3, 177-183 (1994)
[16] Kołcz, [Kołcz and Allinson 96] A.; Allinson, N. M., N-Tuple Regression Network., Neural Network., 9, 5, 855-869 (1996)
[17] Lysenok, [Lysenok et al. 10] I.; Myasnikov, A. G.; Ushakov, A., The Conjugacy Problem in the Grigorchuk Group is Polynomial Time Decidable., Groups, Geom. Dyn., 4, 4, 813-833 (2010) · Zbl 1250.20026
[18] Milnor, [Milnor 68] J., Growth of Finitely Generated Solvable Groups., J. Differ. Geom., 2, 4, 447-449 (1968) · Zbl 0176.29803
[19] Myasnikov, [Myasnikov et al. 11] A. G.; Shpilrain, V.; Ushakov, A.; Mosina, N., Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, 177 (2011), RI, USA: American Mathematical Society Providence, RI, USA · Zbl 1248.94006
[20] Novikov, [Novikov 55] P. S., On the Algorithmic Unsolvability of the Word Problem in Group Theory., Trudy Matem. Inst. imeni V.A. Steklova, 44, 3-143 (1955)
[21] Pedregosa, [Pedregosa et al. 11] F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: Machine Learning in Python., J. Mach. Learn. Res., 12, 2825-2830 (2011) · Zbl 1280.68189
[22] Post, [Post 47] E. L., Recursive Unsolvability of a Problem of Thue., J. Symbolic Logic, 12, 1, 1-11 (1947) · Zbl 1263.03030
[23] Rohwer, [Rohwer and Morciniec 98] R.; Morciniec, M., The Theoretical and Experimental Status of the n-Tuple Classifier., Neural Network, 11, 1, 1-14 (1998)
[24] Shpilrain, [Shpilrain 17] V., Randomness and Complexity in Matrix Groups. (2017) · Zbl 1511.68346
[25] Tattersall, [Tattersall et al. 91] G. D.; Foster, S.; Johnston, Robert D., IEE Proceedings F-Radar and Signal Processing, 138, Single-Layer Lookup Perceptrons., 46-54 (1991), IET
[26] Weiß, [Weiß 16] A., A Logspace Solution to the Word and Conjugacy Problem of Generalized Baumslag-Solitar Groups., Algebra Comput. Sci., 677, 185 (2016) · Zbl 1388.20051
[27] Wolf, [Wolf 68] J. A., Growth of Finitely Generated Solvable Groups and Curvature of Riemannian Manifolds., J. Different. Geom., 2, 4, 421-446 (1968) · Zbl 0207.51803
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.