Colloquium

Let \(G\) be a group given by a finite presentation in terms of generators and relations. For every equality \(w=1\) in \(G\), where \(w\) is a word in the generators, one can construct a planar picture \(\Delta\) (so called Van Kampen diagram). The edges of \(\Delta\) are labeled so that the boundary of \(\Delta\) is labeled by \(w\) while the boundary label of every region of \(\Delta\) is one of the defining relators. The growth rate of the isoperimetric function of such diagrams is responsible for the computational complexity of the word problem in the group \(G\) and its subgroups.

I will give necessary definitions, examples, and discuss the asymptotic behavior of isoperimetric functions and some other asymptotic invariants of groups in connections with the complexity of algorithmic problems for groups. For example (J.Birget, A.Olshanskii, E.Rips, M.Sapir), the word problem is of time complexity NP in a finitely generated group \(G\) if and only if \(G\) is a subgroup of a finitely presented group \(H\) with polynomial isoperimetric function.