The complexity of the equivalence problem for nonsolvable groups

DOI10.1112/BLMS/BDM030MaRDI QIDQ5297585zbMATH OpenOpenAlexFDO

Authors

Publication date 12 July 2007

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/blms/bdm030

zbMATH Keywords

equivalence problemfinite nonsolvable groupspolynomial-time complexityco-NP-complete problemscoloring problem for graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite solvable groups, theory of formations, Schunck classes, Fitting classes, (pi)-length, ranks (20D10) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• Results on the equivalence problem for finite groups.
• The complexity of the equation solvability and equivalence problems over finite groups
• The extended equivalence and equation solvability problems for groups
• The complexity of solving equations over finite groups
• The complexity of the equation solvability problem over nilpotent groups

Cited in

(25)

• An assertion concerning functionally complete algebras and NP-completeness
• The complexity of the equivalence problem over finite rings.
• Notes on extended equation solvability and identity checking for groups
• The complexity of the equation solvability and equivalence problems over finite groups
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• THE EQUIVALENCE PROBLEM OVER FINITE RINGS
• Identity checking problem for transformation monoids
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The equation solvability problem over supernilpotent algebras with Mal’cev term
• scientific article; zbMATH DE number 4097637 (Why is no real title available?)
• Equation satisfiability in solvable groups
• Complexity of the identity checking problem for finite semigroups.
• Identities in twisted Brauer monoids
• On complexity of multiplication in finite soluble groups.
• Satisfiability in MultiValued Circuits
• Word problem of the Perkins semigroup via directed acyclic graphs.
• The extended equivalence and equation solvability problems for groups
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• Identities in upper triangular tropical matrix semigroups and the bicyclic monoid
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• The complexity of the equation solvability problem over semipattern groups
• Results on the equivalence problem for finite groups.
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Complexity issues of checking identities in finite monoids
• A survey on varieties generated by small semigroups and a companion website

This page was built for publication: The complexity of the equivalence problem for nonsolvable groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5297585)