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

co-NP-complete problemscoloring problem for graphsequivalence problemfinite nonsolvable groupspolynomial-time complexity

Mathematics Subject Classification ID

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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)

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

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)