# Group with polynomial-time solvable word problem

From Groupprops

Revision as of 03:03, 1 February 2012 by Vipul (talk | contribs) (Created page with "==Definition== A '''group with polynomial-time solvable word problem''' is a finitely generated group satisfying the following equivalent conditions: # There is a finite...")

## Contents

## Definition

A **group with polynomial-time solvable word problem** is a finitely generated group satisfying the following equivalent conditions:

- There is a finite generating set and an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of , in time bounded by a polynomial function of the length of the word.
- For any finite generating set there is an algorithm that, given any word in terms of the generators, can determine in finite time whether or not that word equals the identity element of , in time bounded by a polynomial function of the length of the word. Note that the coefficients of the polynomial may depend on the choice of the generating set but the degree of the polynomial does not.

This article defines a group property: a property that can be evaluated to true/false for any given group, invariant under isomorphism

View a complete list of group propertiesVIEW RELATED: Group property implications | Group property non-implications |Group metaproperty satisfactions | Group metaproperty dissatisfactions | Group property satisfactions | Group property dissatisfactions

## Relation with other properties

### Stronger properties

Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
---|---|---|---|---|

finitely generated free group | Automatic group|FULL LIST, MORE INFO | |||

finitely generated abelian group | |FULL LIST, MORE INFO | |||

finitely generated nilpotent group | |FULL LIST, MORE INFO | |||

polycyclic group | |FULL LIST, MORE INFO | |||

biautomatic group | Automatic group|FULL LIST, MORE INFO | |||

automatic group | |FULL LIST, MORE INFO | |||

word-hyperbolic group | Automatic group|FULL LIST, MORE INFO |

### Weaker properties

Property | Meaning | Proof of implication | Proof of strictness (reverse implication failure) | Intermediate notions |
---|---|---|---|---|

group with solvable word problem | Group with nondeterministic polynomial-time solvable word problem|FULL LIST, MORE INFO | |||

finitely generated group | Group with solvable word problem|FULL LIST, MORE INFO |