Space functions of groups. (Q2841376)

In the paper under review the author obtains some remarkable results regarding fundamental relations between combinatorial and geometric properties of groups and the complexity of the word problem. This kind of results has a long history dating back to the classical Higman Embedding Theorem [\textit{G. Higman}, Proc. R. Soc. Lond., Ser. A 262, 455-475 (1961; Zbl 0104.02101)], which states that a finitely generated group is recursively presented, i.e. it is defined by a recursively enumerable set of defining relations over a finite set of generators, if and only if it is subgroup of a finitely presented group.NEWLINENEWLINE This result being important for questions of decidability of the word problem is only the first step from a complexity theoretical point of view. In 2002 \textit{M. V. Sapir, J.-C. Birget,} and \textit{E. Rips} [Ann. Math. (2) 156, No. 2, 345-466 (2002; Zbl 1026.20021)] developed some deep connections between isoperimetric functions of finitely presented groups and the (time) complexity of the word problem and in joined work with the author of the paper under review [\textit{J.-C. Birget} et al., Ann. Math. (2) 156, No. 2, 467-518 (2002; Zbl 1026.20018)] they proved an embedding theorem, which can be seen as the (time) complexity analogon of the Higman Embedding Theorem: The word problem of a finitely generated group \(G\) is in \(\mathrm{NP}\), i.e. solvable in polynomial time by a nondeterministic Turing machine, if and only if \(G\) is a subgroup of a finitely presented group with polynomial isoperimetric function.NEWLINENEWLINE One of the main results of the current paper is a space complexity analogon of this statement. For this one needs to replace isoperimetric functions by certain space functions of groups. Several candidates for these functions exist. The notion that is used within this paper was introduced by \textit{M. R. Bridson} and \textit{T. R. Riley} [J. Algebra 307, No. 1, 171-190 (2007; Zbl 1117.20033)] and they call it fragmenting free filling length function. Roughly speaking, for a null-homotopic word \(w\) the function \(\mathrm{FFL}(w)\) measures the minimal combinatorial length \(L\) such that \(w\) admits a combinatorial null-homotopy -- allowing bifurcations -- such that the sum of the lengths of all loops is at most \(L\). In the same way the Dehn function is built out of the number of steps of this null-homotopy the fragmenting free filling length function of the group is built out of \(\mathrm{FFL}(w)\). Introducing the equivalence of functions known from the study of Dehn functions it is easy to check that this space function of a finitely presented group is independent of the chosen finite presentation up to equivalence.NEWLINENEWLINE Then the space complexity embedding theorem can be stated: The word problem of a finitely generated group \(G\) is in \(\mathrm{PSPACE}\), i.e. solvable by a deterministic Turing machine with polynomial space complexity, if and only if \(G\) is a subgroup of a finitely presented group \(H\) having polynomial space function.NEWLINENEWLINE Since it is easy to show that the word problem of a (subgroup of a) finitely presented group with a polynomial space function is solvable by a nondeterministic Turing machine with polynomial space function, the ``if part'' of this theorem is an easy corollary of Savitch's theorem \(\mathrm{PSPACE}=\mathrm{NPSPACE}\) [\textit{W. J. Savitch}, J. Comput. Syst. Sci. 4, 177-192 (1970; Zbl 0188.33502)]. The ``only if'' part is highly nontrivial and, in fact, the author proves an even stronger statement: Let \(H\) be a finitely presented group such that the word problem of \(H\) is decidable by a deterministic Turing machine with space complexity \(f(n)\). Then \(H\) is a subgroup of a finitely presented group \(G\) with space function and logarithm of the Dehn function both equivalent to \(f(n)\).NEWLINENEWLINE This result is obtained in several steps. First the author shows that one can replace the Turing machine by an \(S\)-machine in the sense of Sapir with equivalent space complexity. Then he shows how to simulate the behavior of those machines by van Kampen diagrams and a deep analysis of those diagrams completes the proof.NEWLINENEWLINE Another important result of this paper deals with the question which functions -- up to equivalence -- occur as space functions of groups. Using the same methods mentioned above the author proves the following theorem, which gives a tremendous class of space functions of groups: The space complexity of an arbitrary deterministic Turing machine is equivalent to the space function of some finitely generated group. The author gives several further complexity theoretic applications of these results.