Isoperimetric and isodiametric functions of groups (Q1851484): Difference between revisions

A function \(f\colon\mathbb{N}\to\mathbb{N}\) is called the isoperimetric (isodiametric) function of a symmetrized finite presentation \({\mathcal P}=\langle X\mid R\rangle\) of a group \(G\) if, for any \(n\) and word \(w\) of length \(\leq n\) over \(X\) which is equal to 1 in \(G\), there exists a van Kampen diagram over \(\mathcal P\) whose boundary label is \(w\) and area (diameter) is at most \(f(n)\). The smallest isoperimetric function of \(\mathcal P\) is called the Dehn function of \(\mathcal P\). Note that all finite presentations of the same group have equivalent Dehn functions and equivalent smallest isodiametric functions. (Here two functions \(f,g\colon\mathbb{N}\to\mathbb{N}\) are called equivalent if \(f\preceq g\) and \(g\preceq f\), where \(f\preceq g\) means that there is a nonnegative constant \(c\) such that \(f(n)\leq cg(cn)+cn\), for all \(n\).) It is known that the word problem for \(\mathcal P\) is solvable iff the Dehn function for \(\mathcal P\) is computable. A natural question is which functions are the Dehn functions or the smallest isodiametric functions of finitely presented groups. The paper under review is the first of two important papers devoted to the connection between these functions and computational complexity. It is proven that the Dehn function of any finitely presented group is equivalent to the time function of a two-tape nondeterministic Turing machine; the language accepted by the machine is the set of words equal to 1 in the group. It is shown that, for any language \(L\) recognized by a nondeterministic Turing machine, there exists a finitely presented group such that the nondeterministic time complexity of its word problem is polynomially equivalent to the nondeterministic time complexity of \(L\). In particular, there is a finitely presented group with NP-complete word problem. Modulo some plausible conjectures, the authors describe all Dehn functions \(\succeq n^4\) as time functions of Turing machines. It is shown how to construct finitely presented groups with ``arbitrary weird'' Dehn functions and smallest isodiametric functions. It is proven, in particular, that if a real number \(\alpha\geq 4\) is computable in time \(\preceq 2^{2^{Cm}}\), for some positive constant \(C\), then \(n^\alpha\) is equivalent to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is equivalent to \(n^{3\alpha/4}\). On the other hand, if \(n^\alpha\) is equivalent to the Dehn function of a finitely presented group then \(\alpha\) is computable in time \(\preceq 2^{2^{2^{Cm}}}\), for some positive constant \(C\). An important role in the proofs belongs to a new notion of \(S\)-machine (suggested by Sapir), a version of Turing machine working on the free group. These new machines are proven to be polynomially equivalent to ordinary Turing machines.