The complexity of the equivalence problem for nonsolvable groups
Gábor Horváth, László Mérai, Csaba Szabó, John Lawrence · Bulletin of the London Mathematical Society · 2007
The equivalence problem for a group G is the problem of deciding which equations hold in G. It is known that for finite nilpotent groups and certain other solvable groups, the equivalence problem has polynomial-time complexity. We prove that the equivalence problem for a finite nonsolvable group G is co-NP-complete by reducing the k-coloring problem for graphs to the equivalence problem, where k is the cardinality of G.