Volume: 16, Issue: 5(2006)
pp. 931-939 DOI: 10.1142/S0218196706003256
|
|
Abstract |
Full Text (PDF, 178KB)
|
References
|
 |
| Title: |
THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS |
| Author(s): |
GÁBOR HORVÁTH
Eötvös Loránd University, Department of Algebra and Number Theory, 1117 Budapest, Pázmány Péter sétány 1/C, HungaryCSABA SZABÓ
Eötvös Loránd University, Department of Algebra and Number Theory, 1117 Budapest, Pázmány Péter sétány 1/C, Hungary
|
| History: |
Received 13 June 2005
Revised 31 August 2005
|
| Abstract: |
We analyze the computational complexity of solving a single equation and checking identities over finite meta-abelian groups. Among others we answer a question of Goldmann and Russel from 1998: we prove that it is decidable in polynomial time whether or not an equation over the six-element group S3 has a solution. |
| Keywords: |
Computational complexity; finite groups; identity checking; term equivalence; equation soluability
|
