arXiv Analytics

Sign in

arXiv:2202.05787 [math.GR]AbstractReferencesReviewsResources

The word problem for free groups cannot be solved in linear time*

Alessandro Sisto

Published 2022-02-10Version 1

*by a standard (one-tape) Turing machine. It is well-known that the word problem for hyperbolic groups, whence in particular for free groups, can be solved in linear time. However, these algorithms run on machines more complicated than a standard Turing machine. By contrast, in this note we show that a standard Turing machine cannot solve the word problem for the free group on two generators in less than quadratic time.

Comments: 2 pages
Categories: math.GR, math.CO
Related articles: Most relevant | Search more
arXiv:math/0304209 [math.GR] (Published 2003-04-15)
Diophantine geometry over groups and the elementary theory of free and hyperbolic groups
arXiv:1304.7979 [math.GR] (Published 2013-04-30, updated 2014-10-23)
Growth of Primitive Elements in Free Groups
arXiv:1001.4472 [math.GR] (Published 2010-01-25, updated 2011-12-22)
Statistical properties of subgroups of free groups

Links

Toolbox