The complexity of solving equations over finite groups

Abstract

We study the computational complexity of solving systems of equations over a finite group. An equation over a group G is an expression of the form w/sub 1//spl middot/w/sub 2//spl middot//spl middot//spl middot//spl middot//spl middot/w/sub k/=id where each w/sub i/ is either a variable, an inverted variable, or group constant and id is the identity element of G. A solution to such an equation is an assignment of the variables (to values in G) which realizes the equality. A system of equations is a collection of such equations; a solution is then an assignment which simultaneously realizes each equation. We demonstrate that the problem of determining if a (single) equation has a solution is NP-complete for all nonsolvable groups G. For nilpotent groups, this same problem is shown to be in P. The analogous problem for systems of such equations is shown to be NP-complete if G is non-Abelian, and in P otherwise. Finally, we observe some connections between these languages and the theory of nonuniform automata.