https://groupprops.subwiki.org/w/index.php?title=Group_with_polynomial-time_solvable_word_problem&feed=atom&action=historyGroup with polynomial-time solvable word problem - Revision history2020-02-22T07:44:52ZRevision history for this page on the wikiMediaWiki 1.29.2https://groupprops.subwiki.org/w/index.php?title=Group_with_polynomial-time_solvable_word_problem&diff=38514&oldid=prevVipul: 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..."2012-02-01T03:03:30Z<p>Created page with "==Definition== A '''group with polynomial-time solvable word problem''' is a <a href="/wiki/Finitely_generated_group" title="Finitely generated group">finitely generated group</a> satisfying the following equivalent conditions: # There is a finite..."</p>
<p><b>New page</b></p><div>==Definition==<br />
<br />
A '''group with polynomial-time solvable word problem''' is a [[finitely generated group]] satisfying the following equivalent conditions:<br />
<br />
# 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 <math>G</math>, in time bounded by a polynomial function of the length of the word.<br />
# 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 <math>G</math>, 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.<br />
<br />
{{group property}}<br />
<br />
==Relation with other properties==<br />
<br />
===Stronger properties===<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions<br />
|-<br />
| [[Weaker than::finitely generated free group]] || || || ||{{intermediate notions short|group with polynomial-time solvable word problem|finitely generated free group}}<br />
|-<br />
| [[Weaker than::finitely generated abelian group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|finitely generated abelian group}}<br />
|-<br />
| [[Weaker than::finitely generated nilpotent group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|finitely generated nilpotent group}}<br />
|-<br />
| [[Weaker than::polycyclic group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|polycyclic group}}<br />
|-<br />
| [[Weaker than::biautomatic group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|biautomatic group}}<br />
|-<br />
| [[Weaker than::automatic group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|automatic group}}<br />
|-<br />
| [[Weaker than::word-hyperbolic group]] || || || || {{intermediate notions short|group with polynomial-time solvable word problem|word-hyperbolic group}}<br />
|}<br />
<br />
===Weaker properties===<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions<br />
|-<br />
| [[Stronger than::group with solvable word problem]] || || || || {{intermediate notions short|group with solvable word problem|group with polynomial-time solvable word problem}}<br />
|-<br />
| [[Stronger than::finitely generated group]] || || || || {{intermediate notions short|finitely generated group|group with polynomial-time solvable word problem}}<br />
|}</div>Vipul