# Group with nondeterministic polynomial-time solvable word problem

From Groupprops

## Contents

## Definition

A **group with nondeterministic polynomial-time solvable word problem** is a finitely generated group such that for one (and hence every) word in terms of the generators, the word problem can be solved using a nondeterministic polynomial-time algorithm.

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 |
---|---|---|---|---|

automatic group | ||||

biautomatic group | ||||

combable group | ||||

group satisfying a quadratic isoperimetric inequality | ||||

group satisfying a polynomial isoperimetric inequality | ||||

group with polynomial-time solvable word problem | ||||

finitely generated free group | ||||

finitely generated abelian group |

### Weaker properties

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

group with solvable word problem |