Results on the equivalence problem for finite groups.

DOI10.1007/s00012-004-1895-8zbMath1081.20022OpenAlexW2023679149MaRDI QIDQ2577706

Yanyan Li

Publication date: 6 January 2006

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00012-004-1895-8

zbMATH Keywords

dihedral groupsfinite nilpotent groupspolynomial time complexityco-NP-completepolynomial equivalence problemterm equivalence problem

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Equational logic, Mal'tsev conditions (08B05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Finite nilpotent groups, (p)-groups (20D15) Operations and polynomials in algebraic structures, primal algebras (08A40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Complexity of the identity checking problem for finite semigroups. ⋮ Complexity issues of checking identities in finite monoids ⋮ Satisfiability in MultiValued Circuits ⋮ A survey on varieties generated by small semigroups and a companion website ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identity checking problem for transformation monoids ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ The complexity of the equation solvability problem over semipattern groups ⋮ THE EQUIVALENCE PROBLEM OVER FINITE RINGS ⋮ Word problem of the Perkins semigroup via directed acyclic graphs. ⋮ An assertion concerning functionally complete algebras and NP-completeness ⋮ The complexity of the equation solvability and equivalence problems over finite groups ⋮ COLLAPSING WORDS: A PROGRESS REPORT ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups