Group with polynomial-time solvable word problem

From Groupprops
Jump to: navigation, search

Definition

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

  1. 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 G, in time bounded by a polynomial function of the length of the word.
  2. 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 G, 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 properties
VIEW 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