Isoperimetric functions of groups and computational complexity of the word problem (Q1851485)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Isoperimetric functions of groups and computational complexity of the word problem |
scientific article |
Statements
Isoperimetric functions of groups and computational complexity of the word problem (English)
0 references
5 October 2003
0 references
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\).
0 references
word problem
0 references
van Kampen diagrams
0 references
isoperimetric functions
0 references
Dehn functions
0 references
time complexity
0 references
\(S\)-machines
0 references
finitely generated groups
0 references
finitely presented groups
0 references