Solving the Conjugacy Decision Problem via Machine Learning.

Machine learning and pattern recognition techniques have been successfullyapplied to algorithmic problems in free groups. In this paper, we seek toextend these techniques to finitely presented non-free groups, with aparticular emphasis on polycyclic and metabelian groups that are of interest tonon-commutative cryptography.

As a prototypical example, we utilize supervised learning methods toconstruct classifiers that can solve the conjugacy decision problem, i.e.,determine whether or not a pair of elements from a specified group areconjugate. The accuracies of classifiers created using decision trees, randomforests, and N-tuple neural network models are evaluated for several non-freegroups. The very high accuracy of these classifiers suggests an underlyingmathematical relationship with respect to conjugacy in the tested groups.