International Journal of Algebra and Computation · 2006 · 29 citations · 5 references
ComputingComputer ScienceMathematicsAlgebraAlgorithmsTheory Of ComputationAbstract AlgebraComplexity TheoryComputational ComplexityGroup TheoryComputational Group TheoryFinite Abelian GroupsPolynomial Time ComplexityPolynomial-time Algorithms
We analyze the computational complexity of solving a single equation and checking identities over finite meta-abelian groups. Among others we answer a question of Goldmann and Russel from 1998: we prove that it is decidable in polynomial time whether or not an equation over the six-element group S 3 has a solution.
5
The complexity of solving equations over finite groups
Mikael Goldmann, Alexander Russell · 2003 · 21 citations