×

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\).

MSC:

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
PDFBibTeX XMLCite
Full Text: DOI arXiv