The complexity of solving equations over finite groups

DOI10.1016/S0890-5401(02)93173-1zbMath1012.68087OpenAlexW1999377233MaRDI QIDQ1854566

Alexander Russell, Mikael Goldmann

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(02)93173-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45) Abstract finite groups (20D99) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (28)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ Loosely-abelian algebras ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Satisfiability in MultiValued Circuits ⋮ Some applications of higher commutators in Mal'cev algebras ⋮ The complexity of the equation solvability problem over nilpotent groups ⋮ Equivariant unification ⋮ On properties of multiaffine predicates on a finite set ⋮ Fixed Parameter Tractability and Polynomial Time Results for the Synthesis of b-bounded Petri Nets ⋮ The complexity of the equation solvability problem over semipattern groups ⋮ SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Solving a fixed number of equations over finite groups ⋮ Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras. ⋮ Solving equation systems in ω-categorical algebras ⋮ On solvability of systems of polynomial equations ⋮ A discrete homotopy theory for binary reflexive structures ⋮ Learning expressions and programs over monoids ⋮ Unnamed Item ⋮ Computational complexity and 3-manifolds and zombies ⋮ Unnamed Item ⋮ The equation solvability problem over supernilpotent algebras with Mal’cev term ⋮ TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS ⋮ The complexity of the equation solvability and equivalence problems over finite groups ⋮ Even Faster Algorithms for CSAT Over supernilpotent Algebras. ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups ⋮ The Complexity of Synthesis of b-Bounded Petri Nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-uniform automata over groups
• A Property of Finite Simple Non-Abelian Groups
• Some optimal inapproximability results

This page was built for publication: The complexity of solving equations over finite groups