Change search
ReferencesLink to record
Permanent link

Direct link
The complexity of solving equations over finite groups
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2002 (English)In: Information and Computation, ISSN 0890-5401, E-ISSN 1090-2651, Vol. 178, no 1, 253-262 p.Article in journal (Refereed) Published
Abstract [en]

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(1)(.)w(2)(.)...(.)w(k) = 1(G), where each wi is either a variable, an inverted variable, or a group constant and 1G 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 show 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 problems and the theory of nonuniform automata.

Place, publisher, year, edition, pages
2002. Vol. 178, no 1, 253-262 p.
Keyword [en]
computational complexity, automata, equations, groups
URN: urn:nbn:se:kth:diva-21996DOI: 10.1006/inco.2002.3173ISI: 000178847400011OAI: diva2:340694
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Goldmann, Mikael
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Information and Computation

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link