Isoperimetric functions of groups and computational complexity of the word problem (Q1851485): Difference between revisions

The paper completes the work started by \textit{A.~Yu. Ol'shanskij} [Mat. Sb. 188, No. 1, 51-98 (1997; Zbl 0905.20020)] and \textit{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\).