Open main menu

Groupprops β

Group with polynomial-time solvable word problem

Contents

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