Space functions of groups.

algorithmic word problem decidability of word problem finitely generated groups finitely presented groups generators and relations Higman embedding theorem isoperimetric functions recursively presented groups space complexity space functions of groups van Kampen diagrams

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Generators, relations, and presentations of groups (20F05) Cancellation theory of groups; application of van Kampen diagrams (20F06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Asymptotic properties of groups (20F69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We consider space functions

s (n)

of finitely presented groups

G = < A m i d R > .

(These functions have a natural geometric analog.) To define

s (n)

we start with a word

w

over

A

of length at most

n

equal to 1 in

G

and use relations from

R

for elementary transformations to obtain the empty word;

s (n)

bounds from above the tape space (or computer memory) one needs to transform any word of length at most

n

vanishing in

G

to the empty word. One of the main obtained results is the following criterion: A finitely generated group

H

has decidable word problem of polynomial space complexity if and only if

H

is a subgroup of a finitely presented group

G

with a polynomial space function.

Review text

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.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Space functions of groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841376)