Group with nondeterministic polynomial-time solvable word problem

From Groupprops
Jump to: navigation, search

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