On isomorphism testing of a class of 2-nilpotent groups (Q1174452): Difference between revisions

Let \(G\) be a group. A 3-tuple \((x_ 1,x_ 2,x_ 3)\) of elements of \(G\) satisfies \(P_ 3\) if there exists a nontrivial permutation \(\sigma\) of its components such that \(x_ 1x_ 2x_ 3=x_{\sigma(1)} x_{\sigma(2)} x_{\sigma(3)}\). \(G\) satisfies \(P_ 3\) if every 3-tuple of elements of \(G\) satisfies \(P_ 3\). This paper provides a polynomial time isomorphism test for finite \(P_ 3\)-groups given by means of generators and relations. It is also shown that graph isomorphism testing is uniformly reducible to the word problem of a finitely presented group.