Solving the Conjugacy Decision Problem via Machine Learning
| Autor: | Jonathan Gryak, Robert M. Haralick, Delaram Kahrobaei |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
General Mathematics Group Theory (math.GR) 0102 computer and information sciences Non-commutative cryptography Machine learning computer.software_genre 01 natural sciences Machine Learning (cs.LG) Conjugacy class FOS: Mathematics 0101 mathematics Mathematics business.industry 010102 general mathematics 20F10 68T05 Decision problem Computer Science - Learning 010201 computation theory & mathematics Pattern recognition (psychology) Polycyclic group Artificial intelligence business Mathematics - Group Theory computer Group theory |
| Zdroj: | Experimental Mathematics. 29:66-78 |
| ISSN: | 1944-950X 1058-6458 |
| DOI: | 10.1080/10586458.2018.1434704 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|