论文标题
免费组的单词问题无法在线性时间内解决*
The word problem for free groups cannot be solved in linear time*
论文作者
论文摘要
*通过标准（一挡板）图灵机。众所周知，双曲线群的单词问题，尤其是在自由组中，可以在线性时间内解决。但是，这些算法在机器上运行的是比标准图灵机更复杂的机器。相比之下，在本说明中，我们表明，标准的图灵机无法在不到二次发电机的两个发电机上解决自由组的单词问题。
*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.
