A two-generator, one-relator group is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic time (in the minimum length of the two relators).

This follows by combining a theorem of Steve Pride which says that $\langle a, b\mid R^n\rangle$ and $\langle x, y\mid S^m\rangle$ define isomorphic groups if and only if there is an isomorphism of free groups $\phi:F(a, b)\to F(x, y)$ such that $\phi(R^n)=S^m$ [1], and a theorem of Bilal Khan which says that this latter problem is decidable in quadratic time [2].

The algorithm required here is simply a rephrasing of Whitehead's algorithm, and in the case of rank two Khan improved on Whitehead's algorithm to get a quadratic time algorithm. It is an open problem if Whitehead's algorithm can be improved in arbitrary rank to a polynomial time algorithm. However, it is known to run in quadratic time for "generic" inputs. Similarly, the analogue of Pride's result holds for generic one-relator groups, and so we have the following theorem of Kapovich, Schupp and Shpilrain: The isomorphism problem for generic one-relator groups is decidable in quadratic time [3].

1.Stephen J. Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable. Trans. Amer. Math. Soc. 227 (1977), 109-139. MR 0430085

2.Bilal Khan, The structure of automorphic conjugacy in the free group of rank two, Computational and experimental group theory, Contemp. Math., vol. 349, Amer. Math. Soc., Providence, RI, 2004, pp. 115–196. MR 2077762

3.Ilya Kapovich, Paul Schupp and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006), no.1, 113–140. MR 2221020

A two-generator, one-relator group with torsion is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic time (in the minimum length of the two relators).

This follows by combining a theorem of Steve Pride which says that $\langle a, b\mid R^n\rangle$ and $\langle x, y\mid S^m\rangle$ define isomorphic groups if and only if there is an isomorphism of free groups $\phi:F(a, b)\to F(x, y)$ such that $\phi(R^n)=S^m$ [1], and a theorem of Bilal Khan which says that this latter problem is decidable in quadratic time [2].

The algorithm required here is simply a rephrasing of Whitehead's algorithm, and in the case of rank two Khan improved on Whitehead's algorithm to get a quadratic time algorithm. It is an open problem if Whitehead's algorithm can be improved in arbitrary rank to a polynomial time algorithm. However, it is known to run in quadratic time for "generic" inputs. Similarly, the analogue of Pride's result holds for generic one-relator groups, and so we have the following theorem of Kapovich, Schupp and Shpilrain: The isomorphism problem for generic one-relator groups is decidable in quadratic time [3].

1.Stephen J. Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable. Trans. Amer. Math. Soc. 227 (1977), 109-139. MR 0430085

2.Bilal Khan, The structure of automorphic conjugacy in the free group of rank two, Computational and experimental group theory, Contemp. Math., vol. 349, Amer. Math. Soc., Providence, RI, 2004, pp. 115–196. MR 2077762

3.Ilya Kapovich, Paul Schupp and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006), no.1, 113–140. MR 2221020

A two-generator, one-relator group is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic time (in the minimum length of the two relators).

This follows by combining a theorem of Steve Pride which says that $\langle a, b\mid R^n\rangle$ and $\langle x, y\mid S^m\rangle$ define isomorphic groups if and only if there is an isomorphism of free groups $\phi:F(a, b)\to F(x, y)$ such that $\phi(R^n)=S^m$ [1], and a theorem of Bilal Khan which says that this latter problem is decidable in quadratic time [2].

The algorithm required here is simply a rephrasing of Whitehead's algorithm, and in the case of rank two Khan improved on Whitehead's algorithm to get a quadratic time algorithm. It is an open problem if Whitehead's algorithm can be improved in arbitrary rank to a polynomial time algorithm. However, it is known to polynomial time for "generic" inputs. Similarly, the analogue of Pride's result holds for generic one-relator groups, and so we have the following theorem of Kapovich, Schupp and Shpilrain: The isomorphism problem for generic one-relator groups is decidable in quadratic time [3].

1.Stephen J. Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable. Trans. Amer. Math. Soc. 227 (1977), 109-139. MR 0430085

2.Bilal Khan, The structure of automorphic conjugacy in the free group of rank two, Computational and experimental group theory, Contemp. Math., vol. 349, Amer. Math. Soc., Providence, RI, 2004, pp. 115–196. MR 2077762

3.Ilya Kapovich, Paul Schupp and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006), no.1, 113–140. MR 2221020

A two-generator, one-relator group is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic time (in the minimum length of the two relators).

This follows by combining a theorem of Steve Pride which says that $\langle a, b\mid R^n\rangle$ and $\langle x, y\mid S^m\rangle$ define isomorphic groups if and only if there is an isomorphism of free groups $\phi:F(a, b)\to F(x, y)$ such that $\phi(R^n)=S^m$ [1], and a theorem of Bilal Khan which says that this latter problem is decidable in quadratic time [2].

The algorithm required here is simply a rephrasing of Whitehead's algorithm, and in the case of rank two Khan improved on Whitehead's algorithm to get a quadratic time algorithm. It is an open problem if Whitehead's algorithm can be improved in arbitrary rank to a polynomial time algorithm. However, it is known to run in quadratic time for "generic" inputs. Similarly, the analogue of Pride's result holds for generic one-relator groups, and so we have the following theorem of Kapovich, Schupp and Shpilrain: The isomorphism problem for generic one-relator groups is decidable in quadratic time [3].

1.Stephen J. Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable. Trans. Amer. Math. Soc. 227 (1977), 109-139. MR 0430085

2.Bilal Khan, The structure of automorphic conjugacy in the free group of rank two, Computational and experimental group theory, Contemp. Math., vol. 349, Amer. Math. Soc., Providence, RI, 2004, pp. 115–196. MR 2077762

3.Ilya Kapovich, Paul Schupp and Vladimir Shpilrain, Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups. Pacific J. Math. 223 (2006), no.1, 113–140. MR 2221020