Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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.

36
The categories of this paper are: cmp-lg
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
8
The categories of this paper are: hep-ex
34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
13
The categories of this paper are: quant-ph
27
The categories of this paper are: comp-gas
5
The categories of this paper are: gr-qc
24
The categories of this paper are: dg-ga