Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).

DOI10.1016/j.jpaa.2012.02.007zbMath1259.20041MaRDI QIDQ1934970

Gábor Horváth, Csaba Szabó

Publication date: 30 January 2013

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpaa.2012.02.007

zbMATH Keywords

NP-complete problems; equivalence problem; algorithmic problems; coNP-complete problems; alternating group \(A_4\); equation solvability problem; problem complexities

Mathematics Subject Classification ID

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

20F70: Algebraic geometry over groups; equations over groups

Related Items

The equation solvability problem over supernilpotent algebras with Mal’cev term, Complexity of term representations of finitary functions, Unnamed Item, The complexity of the equation solvability and equivalence problems over finite groups, Satisfiability in MultiValued Circuits, Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras., Loosely-abelian algebras, Identity checking problem for transformation monoids, The complexity of the equation solvability problem over nilpotent groups, Evaluation of polynomials over finite rings via additive combinatorics, The complexity of the equivalence and equation solvability problems over meta-abelian groups, Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions

Cites Work

• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• The complexity of equivalence for commutative rings
• Complexity of the identity checking problem for finite semigroups.
• Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
• The equivalence problem for finite rings
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• Results on the equivalence problem for finite groups.
• Complexity issues of checking identities in finite monoids
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• MONOIDS AND COMPUTATIONS
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• The complexity of the equivalence problem for nonsolvable groups
• Unnamed Item
• Unnamed Item