Isoperimetric functions of groups and computational complexity of the word problem. (English) Zbl 1026.20018

The paper completes the work started by A. Yu. Ol’shanskij [Mat. Sb. 188, No. 1, 51-98 (1997; Zbl 0905.20020)] and M. V. Sapir, J.-C. Birget, E. Rips [Ann. Math. (2) 156, No. 2, 345-466 (2002; see the review Zbl 1026.20021 below)]. The authors prove Birget’s embedding conjecture: a finitely generated group \(G\) has the word problem solvable in polynomial time by a nondeterministic Turing machine if and only if \(G\) is embeddable into a finitely presented group with polynomial isoperimetric function. The embedding can be chosen so that \(G\) has bounded distortion in \(H\).


20F05 Generators, relations, and presentations of groups
20F06 Cancellation theory of groups; application of van Kampen diagrams
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F65 Geometric group theory
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
Full Text: DOI arXiv